Cow Language Valid Words

Farmer John's cows communicate in the unusual Cow language. Each word in this language is a sequence of uppercase and lowercase English letters (A-Z and a-z), and a word is valid if and only if every adjacent pair of letters in the word is an allowed transition.

Farmer John, wary of his cows conspiring, managed to overhear a single word. However, due to the rapid and strange pronunciation of Cow language, he was only able to determine that the word contains U uppercase letters and L lowercase letters.

You are given P valid ordered pairs of letters. Your task is to count the number of valid words that contain exactly U uppercase letters and L lowercase letters such that every adjacent letter pair in the word is one of the allowed pairs. Since the answer can be very large, output it modulo \(97654321\).

Constraints:

• 1 \(\leq U, L \leq 250\)
• 1 \(\leq P \leq 200\)

inputFormat

The input begins with a single line containing three space-separated integers: U, L, and P, representing the number of uppercase letters, the number of lowercase letters, and the number of valid adjacent letter pairs respectively.

The following P lines each contain two characters separated by a space. Each line represents a valid ordered pair indicating that the first letter can be immediately followed by the second letter in a valid word.

outputFormat

Output a single integer which is the number of valid words consisting of exactly U uppercase and L lowercase letters, taken modulo \(97654321\).

sample

1 1 2
A a
a A

2