OI题库

【题目描述】

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

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

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

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

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

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

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

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

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

【输入格式】

一行，有四个整数：P，Q，N，M

【输出格式】

一行，一个整数：外星语言的单词总数模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