Hide

Problem G
Unlock Pattern II

/problems/unlockpattern2/file/statement/en/img-0001.png

Many phones use a nine-pivot unlock pattern. The nine pivots are arranged as a $3 \times 3$ grid, and numbered from $1$ to $9$ as shown in the figure. The unlock pattern is a single stroke that starts at any pivot and visits each pivot exactly once. The stroke goes in a straight line segment between each pair of consecutive pivots. It may pass a pivot multiple times but only the first time counts as a visit. The phone unlocks if the pivots are visited in a predefined secret order. The figure illustrates an unlock pattern of $2 \rightarrow 5 \rightarrow 3 \rightarrow 6 \rightarrow 7 \rightarrow 4 \rightarrow 1 \rightarrow 8 \rightarrow 9$. Due to physical constraints, it is not possible for the stroke to pass but not visit a pivot if it has not been visited before. For instance, a pattern that starts with $1 \rightarrow 7 \rightarrow \dots $ is invalid because it must visit pivot $4$ before visiting pivot $7$. However, starting with $4 \rightarrow 1 \rightarrow 7 \dots $ is fine because pivot $4$ is already visited when the stroke passes it again.

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

Problem GUnlock Pattern II

Input

Output

Problem G
Unlock Pattern II