2081. AlienLanguage

单点时限: 2.0 sec

内存限制: 256 MB

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 P,Q,N,M.

Constraints

-P will be between 1 and 10^9, inclusive.

-Q will be between 1 and 10^9, inclusive.

-N will be between 1 and 10^9, inclusive.

-M will be between 2 and 10^9, inclusive.

输出格式

the maximal number of different words in the aliens’ language modulo M.

样例

Input
1
1
1
9
Output
8
Detail:
If we denote the only vowel as 'a' and the only consonant as 'b' then all different words, not considering stresses, will be: a, b, and ab. With stresses we get 8 words: a, a', b, b', ab, a'b, ab', a'b'.

1 人解决,5 人已尝试。

1 份提交通过,共有 7 份提交。

9.9 EMB 奖励。

创建: 11 年,11 月前.

修改: 2 年,6 月前.

最后提交: 9 年,3 月前.

来源: TC

题目标签