# Unlock Pattern II

Consider the directional changes along the unlock pattern.
The pattern may take a left turn (‘`L`’), a
right turn (‘`R`’), go straight (‘`S`’), or turn around (‘`A`’) at each
pivot except for the first and the last pivot. If we write down
the directional changes into one string, we get a string of
length seven. This is the *turn sequence* of
the unlock pattern. The turn sequence of the unlock pattern
shown in the figure is “`LRRRSRL`”.

Given a turn sequence, with some of the directional changes
replaced by question marks (‘`?`’), which
mean we can take any direction at those pivots, how many
different unlock patterns are consistent with this turn
sequence?

## Input

The input has a single string of length seven. The string
consists of characters ‘`L`’, ‘`R`’, ‘`S`’, ‘`A`’
and ‘`?`’ that describe the directional
changes at the pivots in the order of their visit.

## Output

Output the number of different unlock patterns that have a turn sequence matching the input.

Sample Input 1 | Sample Output 1 |
---|---|

LRRRSRL |
44 |

Sample Input 2 | Sample Output 2 |
---|---|

??AS??? |
0 |