#P3142. [Hnoi2013]数列

    ID: 2297 传统题 1000ms 512MiB 尝试: 1973 已通过: 816 难度: 5 上传者: 标签>CF1700普及+/提高-差分转化乘法原理贡献法等差数列求和快速幂同余的加减乘运算

[Hnoi2013]数列

[HNOI2013] 数列

题目描述

小 TT 最近在学着买股票,他得到内部消息:FF 公司的股票将会疯涨。股票每天的价格已知是正整数,并且由于客观上的原因,最多只能为 NN。在疯涨的 KK 天中小 TT 观察到:除第一天外每天的股价都比前一天高,且高出的价格(即当天的股价与前一天的股价之差)不会超过 MM,MM 为正整数。并且这些参数满足 M(K−1)<NM(K-1)<N。小 TT 忘记了这 KK 天每天的具体股价了,他现在想知道这 KK 天的股价有多少种可能。

输入格式

只有一行用空格隔开的四个数: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 的模值。【输入输出样例】

样例 #1

样例输入 #1

7 3 2 997

样例输出 #1

16

提示

样例解释

输出样例的 1616 表示输入样例的股价有 1616 种可能:

{1,2,3},{1,2,4},{1,3,4},{1,3,5}, {2,3,4},{2,3,5},{2,4,5},{2,4,6}, {3,4,5},{3,4,6},{3,5,6},{3,5,7},{4,5,6},{4,5,7},{4,6,7},{5,6,7}