암호 해독

2차 세계대전 당시, 통신이 필요할 상황에서는 암호를 이용한 통신이 이루어졌습니다. 일본군은 독특한 암호용 언어를 활용했는데, 이 언어는 다른 많은 언어들처럼 각 단어가 대문자와 소문자(A-Z 및 a-z)의 연속된 문자열로 구성되어 있습니다. 단어에 있는 각 인접한 문자 쌍이 유효한 쌍이어야 유효한 단어로 간주됩니다.

미군은 일본군의 암호 통신을 도청하였고, 일본군이 도청을 인지하기 전에 한 단어를 들었습니다. 일본군의 암호용 언어의 발음은 너무 빠르고 독특하여 미군이 정확히 들은 것은 단어 속 대문자의 총 개수 U (1 <= U <= 250)와 소문자의 총 개수 L (1 <= L <= 250)뿐이었습니다.

미군은 모든 P (1 <= P <= 200)개의 유효한 인접 문자 쌍을 알고 있습니다. 그들은 듣고 파악한 제한된 데이터와 일치하는 유효한 단어의 수를 알고 싶어합니다. 하지만 이 경우의 수는 매우 클 수 있으므로, 결과를 97654321로 나눈 나머지 값을 알고자 합니다.

• 첫 번째 줄 : U, L, P를 공백으로 구분한 세 개의 정수
• 두 번째 줄부터 P+1 번째 줄: Cow에서 유효한 인접 문자 쌍을 나타내는 두 글자(대문자 또는 소문자일 수 있음)

• 첫 번째 줄 : 미군의 데이터와 일치하는 유효한 단어의 수를 97654321로 나눈 하나의 정수.