Cowlphabet

모든 소들처럼, 농부 John의 소들도 독특한 '소(Cow)' 언어를 씁니다. 여러 언어가 그렇듯, 이 언어의 각 단어는 대문자와 소문자 알파벳(A–Z, a–z)의 나열입니다. 어떤 단어가 유효하려면, 그 단어 안에서 인접한 모든 순서쌍(앞 글자와 그 뒤에 오는 글자)이 유효한 쌍이어야 합니다.

소들이 자신을 음해할까 늘 걱정하던 농부 John은 최근 소들의 대화를 엿들으려다, 들키기 직전에 단어 하나를 겨우 들었습니다. 소 언어는 너무 빠르고 발음이 낯설어서, 그가 알아낼 수 있었던 것은 그 단어에 들어 있는 대문자의 총 개수 $U$ ($1 \le U \le 250$)와 소문자의 총 개수 $L$ ($1 \le L \le 250$)뿐이었습니다.

농부 John은 소 언어에서 인접할 수 있는 유효한 순서쌍 $P$개($1 \le P \le 200$)를 모두 알고 있습니다. 그는 이 제한된 정보와 들어맞는 유효한 단어가 몇 개인지 알고 싶어 합니다. 이 값이 매우 커질 수 있으므로, $97654321$로 나눈 나머지를 구하면 됩니다.

• 첫째 줄: 공백으로 구분된 세 정수 $U$, $L$, $P$.
• 둘째 줄부터 $P+1$째 줄까지: 각 줄에 유효한 순서쌍을 이루는 두 글자(각각 대문자 또는 소문자일 수 있음). 앞 글자 바로 뒤에 뒤 글자가 이어질 수 있음을 뜻합니다.

• 첫째 줄: 농부 John의 정보와 들어맞는 유효한 단어의 개수를 $97654321$로 나눈 나머지 하나.

• 단어는 글자들의 순서 있는 나열이며, 같은 글자가 여러 번 나올 수 있습니다.
• $U$와 $L$은 단어 전체에서의 대문자·소문자 총 개수이며, 각 글자가 놓이는 위치는 상관없습니다.
• 글자 나열이 다르면 서로 다른 단어로 셉니다.
• $U \ge 1$, $L \ge 1$이므로 모든 단어의 길이는 2 이상이고, 단어에 쓰인 각 글자는 적어도 하나의 인접 쌍에 속합니다.