Maishroom & Table

时间限制:10s      空间限制:256MB

题目描述

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。


输入格式

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


输出格式

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


样例输入

2 2 2 1000000007	

样例输出

9

提示

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


题目来源

没有写明来源