유니콘
시간 제한2초메모리 제한128 MB
N x M 격자에서 유니콘 기물이 주어진 단어를 순서대로 그리는 경로의 개수를 1,000,000,007로 나눈 나머지로 구합니다.
문제
유니콘은 체스의 나이트와 비슷한 말이다. 나이트는 한 방향으로 2칸, 그 방향과 수직인 방향으로 1칸 움직인다. 반면 유니콘은 네 기본 방향 중 하나로 2칸보다 많이 움직인 뒤, 방금 움직인 방향과 수직인 두 방향 중 하나로 1칸보다 많이 움직인다.
더 정확히 말하면, 유니콘의 한 번의 이동은 다음과 같다.
- 유니콘을 든다.
- 네 기본 방향 중 하나로 칸 이상 움직인다.
- 방금 움직인 방향과 수직인 두 방향 중 하나로 칸 이상 움직인다.
- 유니콘을 놓는다.
체스판의 크기는 이다. 각 칸에는 알파벳 대문자의 처음 개 문자 중 하나가 쓰여 있다.
, , 과 단어가 주어진다. 유니콘이 놓이는 칸들의 문자가 주어진 단어와 순서대로 일치하는 경로의 수를 구하라. 답은 로 나눈 나머지로 출력한다.
입력
첫째 줄에 , , 이 주어진다. 과 은 이하의 자연수이고, 은 이하의 자연수이다.
둘째 줄에 단어가 주어진다. 단어의 길이는 최대 이며, 알파벳 대문자로만 이루어져 있다.
셋째 줄부터 개의 줄에 체스판에 적힌 문자열이 주어진다. 각 문자열의 길이는 이다.
출력
첫째 줄에 경로의 수를 로 나눈 나머지를 출력한다.