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?
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 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 |