Time Limit: 1000 MS Memory Limit: 65536 K
Yesterday a very strange piece of paper was found by an international group of scientists.
They believe ití»s about 1 million years old! Moreover, it contains some text written in
an alien language. Here are all the known facts about this language:
1. The aliens' alphabet consists of exactly P vowels and Q consonants.
2. Each word contains no more than N vowels and no more than N consonants.
3. In each word, the vowels always precede the consonants, i.e., each word consists
of a consecutive block of vowels followed by a consecutive block of consonants. The length
of either block can be zero.
4. Each word contains at least one letter.
5. Each word can have stresses. Aliens put stresses not on syllables but on letters!
There are three possibilities: the word has no stresses, the word has one stress (on one of
its letters), or the word has two stresses (one on a vowel and one on a consonant).
6. Two words that contain the same exact letters in the same order, but have different
stresses, are considered different.
The scientists want to know the maximal number of different words in the aliens' language. Help them!
Return the maximal number of different words in the aliensí» language modulo M.
There are many test cases.For each test case there are four integers P Q N and M.
( 1 <= P,Q,N <= 10^9 )
( 2 <= M <= 10^9 )
For each test case output the answer on a single line.
2 3 2 1000
TopCoder SRM 377