시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 851 | 241 | 193 | 32.712% |
유니콘은 체스에서 나이트와 비슷한 말이다. 단, 나이트는 두 칸을 한 방향으로 움직이고, 또 다른 한 칸을 다른 방향으로 움직이지만, 유니콘은 두 칸보다 많은 칸을 한 방향으로 움직이고, 한 칸보다 많은 칸을 또다른 방향으로 움직인다.
좀 더 정확하게 유니콘이 움직이는 방법을 살펴보면 다음과 같다.
체스판의 크기는 $N \times M$이다. 체스판의 각 칸에는 알파벳 대문자의 처음 $L$개의 문자 중 하나가 쓰여 있다.
$N$, $M$, $L$, 그리고 단어가 주어진다. 유니콘이 움직인 경로 (유니콘을 놓은 곳)가 입력으로 주어진 단어와 일치하는 경우의 수를 출력하는 프로그램을 작성하시오.
첫째 줄에 $N$, $M$, $L$이 주어진다. $N$과 $M$은 $300$보다 작거나 같은 자연수이다. $L$은 $26$보다 작거나 같은 자연수이다. 둘째 줄에 단어가 주어진다. 단어의 길이는 최대 $50$이며, 알파벳 대문자로만 이루어져 있다. 셋째 줄 부터 $N$개의 줄에 체스판에 쓰여 있는 단어가 주어진다.
첫째 줄에 경로를 $1\,000\,000\,007$로 나눈 나머지를 출력한다.
3 4 2 AB ABBA AAAA BBBB
2
5 5 2 CD ABBAA AAABB BBBBB ABABA ABBBB
0
4 4 1 AA AAAA AAAA AAAA AAAA
20
4 4 1 AAAAA AAAA AAAA AAAA AAAA
172
1 1 5 ABCDE C
0
8 8 26 TOPCODER AILFPSPF DZIOMYCE QOODZARU YVOTLTRX LSRIGANL LCIUUSNF IWVXKTDE OVPPNXRD
1
20 20 2 AAAAA ABBAAAAABBBBBBBABABA ABBBBBABAAAABBAAABAA BAAABAABAABBABABBABB BBABBAAAABABAAAAABBA BBABAABABBAABABABBBA BABABAABABBBABBAABBA BAABBAAABBBABBABAAAA BAABBBBABAABAAAAABAA AABABAAAAABBBABABBBA BBAABAAABBAABAAAAABA BAAAAABABBAAABABABBA ABBAABBBABABBABAAABB AAAABAAAAAAAABBBAABB AAABABAAAAAABAAABABB AAABABABBABABAAABBBA AAABBBBAABBAABAAABBA BBBBAAABBABABAAAABAB BBAABBAABAAAABAABABA BBBAABBABABBBBBBBBBA AAABABBBBAABABBBBBBB
373977054