P3012 [USACO11FEB] Cowlphabet G

Like all bovines, Farmer John's cows speak the peculiar "Cow" language. As in many languages, each word in this language is a sequence of uppercase and lowercase letters (A-Z and a-z). A word is valid if and only if each ordered pair of adjacent letters in the word is a valid pair. Farmer John, ever worried that his cows are plotting against him, recently tried to eavesdrop on their conversation. He overheard one word before the cows noticed his presence. The Cow language is spoken so quickly, and its sounds are so strange, that all Farmer John was able to perceive was the total number of uppercase letters, $U$ ($1 \leq U \leq 250$), and the total number of lowercase letters, $L$ ($1 \leq L \leq 250$), in the word. Farmer John knows all $P$ ($1 \leq P \leq 200$) valid ordered pairs of adjacent letters. He wishes to know how many different valid words are consistent with his limited data. However, since this number may be very large, he only needs the value modulo $97654321$.

- Line 1: Three space-separated integers: $U$, $L$, and $P$. - Lines 2 to $P+1$: Two letters $A_i$ and $B_i$ (each of which may be uppercase or lowercase), representing one valid ordered pair of adjacent letters in Cow, meaning $A_i$ can be followed by $B_i$. No ordered pair appears more than once.

- Line 1: A single integer, the number of valid words consistent with Farmer John's data, modulo $97654321$.

The word Farmer John overheard had 2 uppercase and 2 lowercase letters. The valid pairs of adjacent letters are AB, ab, BA, ba, Aa, Bb and bB. The possible words are: AabB ABba abBA BAab BbBb bBAa bBbB Translated by ChatGPT 5