1471. [SRM 377] 外星语言

【题目描述】

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

$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 \leq N,P,Q \leq 10^9,1 \leq M \leq 10^9$

【来源】

$TopCoder$ $Algorithm$ $SRM$ $377$, $Div$ $1$, $1000$