本题无额外样例下载。
题目描述
已知有三个正整数 H,N,M,满足 M(N−1)<H。
现在让你构造一个数列 A,满足:
(1)数列中含有 N 个元素;
(2)每个元素均为不超过 H 的正整数,即 1≤Ai≤H。
(3)数列是严格上升的,即 Ai<Ai+1。
(4)任意相邻两个数的差不超过 M,即 Ai+1−Ai≤M。
问:你能构造出多少个满足条件的数列?答案可能很大,你需要输出答案 mod P。
输入格式
一行,包含四个整数:H、N、M、P。
输出格式
一个整数,表示答案 mod P
输入样例1
5 3 2 10
输出样例1
8
样例解释1
有 8 种可能:
<1,2,3>,<1,2,4>,<1,3,4>,<1,3,5>,<2,3,4>,<2,3,5>,<2,4,5>,<3,4,5>
输入样例2
123456789876543210 135797531 246808642 123456789
输出样例2
71065463
数据范围
30% 的数据:1≤M,H,N,P≤2×104
100% 的数据:1≤M,N,P≤109,1≤H≤1018。