8308: BZOJ4308：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是素数。

题目来源

没有写明来源