30519번 - 짜고 치는 가위바위보 (Large)

문제

가위바위보 챔피언십이 열렸다. 수많은 관중이 지켜보고 있다. 이 상황에서 lighter와 smallant는 가위바위보 챔피언십 결승에 도달했다. 하지만 둘은 어릴 적부터 너무 친한 친구라, 누가 이기든 별로 신경 쓰지 않는다. 따라서 두 사람은 이번 결승에서 재미있는 장난을 치려고 한다.

결승전은 여러 라운드의 가위바위보로 진행된다. lighter는 첫 번째 라운드를 제외하고, smallant가 바로 이전 라운드에 냈던 것을 따라 내는 장난을 치고자 한다. 하지만, 이런 장난은 관중이 정말 싫어한다. lighter가 이긴 뒤 직후 라운드에서 비기는 결과가 나온다면, 관중은 두 사람이 장난을 친다는 사실을 알아채서 분노할 것이다.

관중이 분노하면 챔피언십의 후원이 끊길 수도 있기 때문에, smallant는 앞에 무엇을 낼지를 다시 생각해볼 필요가 있었다. 곰곰이 생각한 smallant는 기존에 내고자 했던 가위바위보의 정보 중 일부분만 취하면 문제가 해결됨을 알았다.

일부분만 취한다는 뜻은 기존에 내고자 했던 가위바위보의 정보가 문자열로 주어졌을 때, 그중 몇 개의 문자를 제거하여 순서를 바꾸지 않고 합치는 것을 의미한다.

예를 들어, 결승이 8라운드로 구성되었다고 해보자. smallant는 첫 번째 라운드부터 여덟 번째 라운드까지 <표 1>에 나온 것과 같이 낸다고 하자. 즉, 보, 가위, 보, 가위, 보, 보, 주먹, 가위 순으로 낼 것이다. 이때 lighter는 첫 번째 라운드만 주먹을 내고 그 이후 라운드부터는 smallant를 따라 낸다.

<표 1>

이 경우, 다섯 번째 라운드에서 lighter가 이기고 그 직후 라운드에 비겼으므로, 관중이 분노할 것이다.

따라서, 이 경우는 <표 2>와 같이 smallant가 기존에 내고자 했던 보, 가위, 보, 가위, 보, 보, 주먹, 가위의 순서에서, 여섯 번째와 일곱 번째를 제외한 보, 가위, 보, 가위, 보, 가위의 순서로 결승을 진행하면 된다.

<표 2>

smallant가 내고자 했던 가위바위보의 정보가 주어졌을 때, 관중이 분노하지 않도록 smallant가 내고자 했던 가위바위보의 정보를 일부분만 취하는 경우의 수를 구해보자. 단, 최소 하나의 라운드는 존재해야 한다.

입력

R은 바위를, P는 보를, S는 가위를 의미한다.

첫 번째 줄에는 lighter가 첫 번째 라운드에서 무엇을 낼지에 대한 정보가 알파벳 대문자 R 또는 P 또는 S로 주어진다.

두 번째 줄에는 smallant가 결승에서 무엇을 낼지에 대한 정보가 R 또는 P 또는 S로 구성된 길이가 1ドル$ 이상 1ドル\ 000\ 000$ 이하인 문자열로 주어진다.

출력

관중이 분노하지 않도록 smallant가 내고자 했던 가위바위보의 정보를 일부분만 취하는 경우의 수를 소수 1ドル\ 000\ 000\ 007$로 나눈 나머지를 출력한다.

제한

힌트