考虑我们把所有的增加量拿出来做成一个序列b。

　　那么在所有n中开头中$1~\sum\limits_{i=1}^{k-1}b[i]$是合法的

　　也就是说我们枚举所有b[i],然后答案就是$n*m^{k-1}-\sum\sum b[i]$

　　后面那个“对所有可能的序列b的序列和求和”怎么算呢？

　　考虑到题目中神奇的限制m*(k-1)<n，也就是说b序列的任意一位1~m都是随便取的

　　因此等差数列求1~m前缀和乘上每个数出现的次数即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;inline long long read(){    long long num=0,f=1;    char ch=getchar();    while(!isdigit(ch)){        if(ch=='-')    f=-1;        ch=getchar();    }    while(isdigit(ch)){        num=num*10+ch-'0';        ch=getchar();    }    return num*f;}long long n,m,e,mod;long long Pow(long long a,long long b){    long long ret=1;    while(b){        if(b&1)    ret=ret*a%mod;        a=a*a%mod;        b>>=1;    }    return ret;}int main(){    n=read(),e=read(),m=read(),mod=read();    long long ans=(n%mod)*Pow(m,e-1)%mod;    long long now=(1+m)*m/2%mod*(e-1)%mod*Pow(m,e-2);    printf("%lld\n",((ans-now)%mod+mod)%mod);    return 0;}