UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4308. Maishroom & Table

Statistics 下载数据

Description

Maishroom拿到了一张H格高W格宽的数表,其中左上角的数是0,其他数都在0到S之间(含)。Maishroom想从左上角走到右下角,每一步只能向下或向右走,使得路径上数之和最大。
这是个有趣的题目,因为有一个正确性显然不对的贪心算法。
Greedily_Act(Now_h, Now_w)
If Now_w == W
    MOVE_DOWN
Else If Now_h == H
    MOVE_RIGHT
Else If V[Now_h][Now_w + 1] >= V[Now_h + 1][Now_w]
    MOVE_RIGHT
Else
    MOVE_DOWN
End
Maishroom知道你们用脚趾头都能做出原来那道题,
于是现在他的问题是:求出有多少种数表,满足在该贪心算法下的答案为S。

Input

一行四个整数,H, W, S, P。P是素数。

Output

一个整数,为答案对P取模的结果。

Sample Input

2 2 2 1000000007

Sample Output

9

Hint

对于100%的数据:1≤H, W, S≤10^6, 108≤P≤2^30,P是素数。


Source