题目链接：

 

题意：给出n，K，m，p。求有多少长度为K的序列A，满足：（1）首项为正整数；（2）递增数列；（3）相邻两项的差小于等于m；（4）最大值小于等于n。

 

思路：设相邻两项的差值为a[i]=A[i+1]-A[i]，那么每一个这样的序列对答案的贡献为:

i64 n,K,m,p;i64 Pow(i64 a,i64 b){    i64 ans=1;    while(b)    {        if(b&1) ans=ans*a%p;        a=a*a%p;        b>>=1;    }    return ans;}int main(){    RD(n,K); RD(m,p);    i64 ans=n%p*Pow(m,K-1)%p-m*(m+1)/2%p*Pow(m,K-2)%p*(K-1)%p;    ans%=p;    if(ans<0) ans+=p;    PR(ans);}