#1978. [HNOI2013] 数列

[HNOI2013] 数列

题目描述

小 T 最近在学着买股票,他得到内部消息:F 公司的股票将会疯涨。股票每天的价格已知是正整数,并且由于客观上的原因,最多只能为 NN。在疯涨的 KK 天中小 T 观察到:除第一天外每天的股价都比前一天高,且高出的价格(即当天的股价与前一天的股价之差)不会超过 MM,MM 为正整数。并且这些参数满足 $M(K-1)

输入格式

只有一行用空格隔开的四个数:NN、KK、MM、PP。对 PP 的说明参见后面“输出格式”中对 PP 的解释。输入保证 20%20\% 的数据 M,N,K,P≤20000M,N,K,P \le 20000,保证 100%100\% 的数据 M,K,P≤109M,K,P \le 10^9,N≤1018N \le 10^{18}。

输出格式

仅包含一个数,表示这 KK 天的股价的可能种数对于 PP 的模值。

样例

7 3 2 997
16

题目来源:洛谷 P3228