모든 종류의 소들과 마찬가지로, 농부 존의 소들은 그들의 독특한 ‘소 언어’를 쓴다. 많은 언어와 비슷하게, 이 언어의 단어들은 일련의 대문자와 소문자(A-Z, a-z)로 이뤄져 있고, 단어는 연속해서 연결된 순서쌍들(두개의 문자)의 집합으로, 단어 내의 모든 순서쌍들이 유효할 때만 단어가 유효하다고 할 수 있다.

존은 자신의 소들이 역모를 꾸밀까봐 우려하고 있다. 이 때문에 최근에 소들의 대화를 도청하려다가 들켜버린 그는 들키기 전에 다행히 하나의 단어를 엿들었다. ‘소 언어’는 매우 빠르고, 아주 이상하기 때문에 존이 알 수 있던 것은 그 단어의 총 대문자의 개수 U (1 <= U <= 250)와 소문자의 개수 L (1 <= L <=250) 뿐이었다.

존은 모두 P (1 <= P <= 200) 개의 유효 순서쌍을 알고 있다. 그는 엿들은 정보로 단어의 조합이 유효한 경우가 몇 가지나 나오는지 알고 싶다. 단, 이 수가 매우 커질 수 있으므로 97654321로 나눈 나머지를 구해주자.

입력

• 첫째 줄 : U와 L 그리고 P가 공백으로 구분되어 입력된다.
• 둘째 줄부터 P+1번째 줄까지 : 두 개의 글자(각각의 글자는 대문자 또는 소문자이다)로써, 하나의 유효한 순서쌍을 나타낸다.

출력

입출력 예

입력 

2 2 7 
AB 
ab 
BA 
ba 
Aa 
Bb 
bB 

출력 

7 

입출력 보충

입력 보충 : 
농부 존이 엿들은 정보는 2개의 대문자와 2개의 소문자로 이뤄졌다. 
유효한 순서쌍들은 AB, ab, BA, ba, Aa, Bb 그리고 bB이다. 

출력 보충 : 
가능한 단어는 
AabB 
ABba 
abBA 
BAab 
BbBb 
bBAa 
bBbB 
이렇게 7개이다.

출처:usaco FEB11 gold
번역:shinism