Crossing the Stone Bridges

An expedition must cross two parallel stone bridges to obtain a ring. One bridge is the , and the other is the .

The two bridges always have the same length. Each stone contains one of the characters R, I, N, G, and S. The table below shows one bridge pair of length 6.

A magic scroll lists the characters that must be stepped on in order while crossing the bridges. If the expedition breaks this order, the bridges collapse.

A valid crossing must satisfy all of the following rules.

1. Movement is only from the starting side to the finishing side, that is, from left to right.
2. Every character written on the scroll must be stepped on in the given order.
3. The chosen bridge must alternate between the and the at every step. The first stone may be on either bridge.
4. Each next stone must be strictly to the right of the previous stone. Moving at least one column is enough, and any number of stones may be skipped.

For the bridge pair shown above, if the scroll is RGS, there are exactly 3 valid crossing methods. Given the scroll string and the two bridge strings, compute the total number of valid crossing methods.

The first line contains the string written on the magic scroll. It consists only of R, I, N, G, and S, and its length is between 1 and 20 inclusive.

The second and third lines contain the strings written on the and the , respectively. The two strings have the same length, and that length is between 1 and 100 inclusive.

Print the number of ways to cross the bridges while following the scroll in order. If there is no valid way, print 0.

For every test case, the answer is at most 2^31 - 1.