2872. Cowlphabet

单点时限: 2.0 sec

内存限制: 256 MB








Like all bovines, Farmer John's cows speak the peculiar 'Cow'

language. Like so many languages, each word in this language comprises

a sequence of upper 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 that

Farmer John was able to perceive was the total number of uppercase

letters, U (1 <= U <= 250) and the total number of lowercase

letters, L (1 <= L <= 250) in the word.

Farmer John knows all P (1 <= P <= 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..P+1: Two letters (each of which may be uppercase or

lowercase), representing one valid ordered pair of adjacent

letters in Cow.

输出格式









* Line 1: A single integer, the number of valid words consistent with

Farmer  John's data mod 97654321.

样例

Input
2 2 7
AB
ab
BA
ba
Aa
Bb
bB
INPUT DETAILS:
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.
Output
7
OUTPUT DETAILS:
The possible words are:
AabB
ABba
abBA
BAab
BbBb
bBAa
bBbB

2 人解决,5 人已尝试。

2 份提交通过,共有 8 份提交。

9.2 EMB 奖励。

创建: 8 年,10 月前.

修改: 2 年,4 月前.

最后提交: 6 年,1 月前.

来源: USACO 2011 FEB GOLD

题目标签