Maishroom & Table

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是素数。