[SRM 377]外星语言

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file alienlanguage.in Output file alienlanguage.out

【题目描述】

一个国际科研小组昨天发现了一张奇奇怪怪的纸片。他们相信它大约有一百万年的历史。而且,它包含了一些用外星语言写下的文本。下面是对于这种外星语言的所有已知事实:

1.         外星语言的字母表由P个元音和Q个辅音构成。

2.         外星语言的每个单词包含了至多N个元音和至多N个辅音。

3.         在单词中元音总是在辅音之前,即每个单词由一段辅音和后面紧跟着的一段元音构成。
元音或辅音的个数都可以是零。

4.         每个单词至少包含一个字母。

5.         每个单词都可以有重音。外星人将重音标记在字母而非音节上。有三种可能的情况:单词没有重音,单词由一个重音(它可以在任一个字母上),单词有两个重音(一个在元音字母上,一个在辅音字母上)。

6.         两个字母拼写完全相同,但重音不同的单词是不同的。

科学家们希望知道外星语言中单词的总数。他们把这个任务作为练习留给了你。

你的程序被要求返回外星语言中单词的总数模M的值。

【输入格式】

一行,有四个整数:PQNM

【输出格式】

一行,一个整数:外星语言的单词总数模M的值

【样例输入】

sample1:
1 1 1 9

sample2:
2 3 2 1000

sample3:
1 1 1000000000 1000000000

sample4:
123 456 789 987654321

【样例输出】

sample1:
8

sample2:
577

sample3:
0

sample4:
345494202

【提示】

1<=N,P,Q<=10^9
1<=M<=10^9

【来源】

TopCoder Algorithm SRM 377, Div 1, 1000