Time Limit: 1000 MS    Memory Limit: 65536 K 


Description

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.

Input

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 )

Output

For each test case output the answer on a single line.

Sample Input

2 3 2 1000

Sample Output

577

Source

TopCoder SRM 377