돌다리 건너기

절대반지를 얻기 위해 원정대가 두 개의 나란한 돌다리를 건너려고 한다. 두 돌다리 중 하나는 <악마의 돌다리>, 다른 하나는 <천사의 돌다리>이다.

두 돌다리의 길이는 항상 같고, 각 칸에는 R, I, N, G, S 중 하나의 문자가 새겨져 있다. 아래 표는 길이가 6인 돌다리의 한 모습이다.

원정대가 가진 마법의 두루마리에는 다리를 건널 때 반드시 순서대로 밟아야 하는 문자들이 적혀 있다. 순서를 어기면 돌다리가 무너진다.

다리를 건널 때는 다음 규칙을 모두 만족해야 한다.

1. 출발 지점에서 도착 지점 방향, 즉 왼쪽에서 오른쪽으로만 이동한다.
2. 두루마리에 적힌 문자열의 모든 문자를 순서대로 밟아야 한다.
3. 밟는 돌다리는 매번 <악마의 돌다리>와 <천사의 돌다리>가 번갈아야 한다. 첫 번째 돌은 어느 돌다리에서 시작해도 된다.
4. 다음으로 밟는 돌은 이전에 밟은 돌보다 반드시 오른쪽에 있어야 한다. 한 칸 이상만 전진하면 되며, 중간의 돌은 몇 칸이든 건너뛸 수 있다.

위 표에서 두루마리의 문자열이 RGS라면 규칙을 만족하며 건널 수 있는 방법은 3가지이다. 주어진 두루마리 문자열과 두 돌다리의 문자열에 대해, 모든 가능한 건너기 방법의 수를 구하라.

첫째 줄에 마법의 두루마리에 적힌 문자열이 주어진다. 이 문자열은 R, I, N, G, S로만 이루어져 있으며, 길이는 1 이상 20 이하이다.

둘째 줄과 셋째 줄에는 각각 <악마의 돌다리>와 <천사의 돌다리>에 새겨진 문자열이 주어진다. 두 문자열의 길이는 같고, 길이는 1 이상 100 이하이다.

두루마리에 적힌 문자열의 순서대로 다리를 건널 수 있는 방법의 수를 출력한다. 가능한 방법이 없으면 0을 출력한다.

모든 테스트 데이터에서 정답은 2^31 - 1 이하이다.