19543번 - 던전 지도

동현이는 로그라이크 던전 탐험 게임을 개발하고 있다. 이 게임에서 던전은 $N$행 $M$열의 격자 형태로 방이 놓여 있는 구조이다. 아래쪽에서 $i$번째 행의 왼쪽에서 $j$번째에 있는 방을 $\left(i, j\right)$라고 하자.

던전의 각 방에는 R 또는 U가 적혀 있다. 플레이어는 던전의 임의의 방에서부터 시작해 방을 하나씩 깨 나가는데, 이번에 깬 방이 $\left(i, j\right)$일 때 그 방에 R이 적혀 있었다면 $\left(i, j + 1\right)$로 이동하고, U가 적혀 있었다면 $\left(i + 1, j\right)$로 이동한다. 만약 새로 이동할 좌표에 해당하는 방이 없다면 던전을 탈출하게 된다.

동현이는 던전 지도를 효율적으로 만들기 위해 다음과 같은 방식을 사용하였다.

• 지도의 한 행을 구성하는 $K$종류의 블록을 미리 만들어 놓고, 각 블록에 알파벳 대문자의 처음 $K$글자 중 하나를 대응시킨다. 각 블록은 R과 U로만 이루어진 길이 $M$의 문자열이다.
• 알파벳 대문자의 처음 $K$종류로 이루어진 길이 $N$의 문자열을 하나 생성한 뒤, 그 문자열의 $i$번째 글자에 대응되는 블록으로 던전의 아래에서 $i$번째 행을 만든다.

던전의 가장 오른쪽 위, 즉 $\left(N, M\right)$은 보스 방으로, 던전에서 가장 어려운 방인 대신 깨면 막대한 보상이 주어진다. 시작 위치에 따라 보스 방에 도달 가능할 수도 있고 없을 수도 있는데, 동현이는 지금 만든 지도에서 과연 보스 방에 도달할 수 있는 시작 방이 몇 개나 되는지 궁금해졌다.

하지만, 동현이는 지도 생성 말고도 할 일이 많다. 여러분이 동현이를 대신해 의문점을 해결해 주자!

첫 번째 줄에 던전의 행 개수 $N$, 열 개수 $M$, 블록의 종류 $K$가 공백으로 구분되어 주어진다. ($1 \leq N, M \leq 200\ 000$, $1 \leq K \leq 26$)

두 번째 줄부터 $K$개의 줄에 R과 U로만 이루어진 길이 $M$의 문자열이 주어진다. 이 $K$개의 줄 중 $i$번째 줄은 $i$번째 알파벳 대문자에 대응되는 블록이다.

그 다음 줄에 알파벳 대문자의 처음 $K$종류로만 이루어진 길이 $N$의 문자열이 주어진다. 이 문자열의 $j$번째 글자는 던전의 아래에서 $j$번째 행을 구성하는 블록을 의미한다.

첫 번째 줄에 주어진 지도에서 $\left(N, M\right)$에 도달할 수 있는 시작 방의 개수를 출력한다. $\left(N, M\right)$도 시작 방이 될 수 있음에 유의하라.