Description
小T最近在学着买股票，他得到内部消息：F公司的股票将会疯涨。股票每天的价格已知是正整数，并且由于客观上的原因，最多只能为N。在疯涨的K天中小T观察到：除第一天外每天的股价都比前一天高，且高出的价格（即当天的股价与前一天的股价之差）不会超过M，M为正整数。并且这些参数满足M(K-1)<N。
小T忘记了这K天每天的具体股价了，他现在想知道这K天的股价有多少种可能
Input
只有一行用空格隔开的四个数：N、K、M、P。对P的说明参见后面“输出格式”中对P的解释。
输入保证20%的数据M,N,K,P≤20000，保证100%的数据M,K,P≤109，N≤1018 。
Output
仅包含一个数，表示这K天的股价的可能种数对于P的模值。【输入输出样例】
Sample Input
7 3 2 997
Sample Output
16
Solution
设每天的股价为(a[1]...a[k])，考虑它的差分序列(s[1]...s[k-1])。
由于最多不能超过(n)，所以(a[1])的取值就有(n-sum_{i=1}^{k-1}s[i])种情况。
考虑差分序列每一位最多是(m)，所以差分序列一共有(m^{k-1})种，设第(d)种第(i)位为(s[d][i])，
所以答案就是：
[egin{align}
&sum_{d=1}^{m^{k-1}}(n-sum_{i=1}^{k-1}s[d][i])\
=&ncdot m^{k-1}-sum_{d=1}^{m^{k-1}}sum_{i=1}^{k-1}s[d][i]
end{align}
]
考虑到后面一项共有(m^{k-1}cdot (k-1))，而(s[d][i])又在([1,m])上均匀分布，所以最后一项就等于：
[m^{k-2}cdot (k-1)cdot frac{m(m+1)}{2}
]
然后带上去快速幂一下就行了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ONLINE_JUDGE
#ifdef ONLINE_JUDGE
#define getchar() ((p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin)),p1==p2)?EOF:*p1++)
#endif
namespace fast_IO {
char buf2[1<<21],a[80];int p,p3=-1;
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T> inline void read(T &x) {
x=0;T f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
template <typename T,typename... Args> inline void read(T& x,Args& ...args) {
read(x),read(args...);
}
inline void flush() {fwrite(buf2,1,p3+1,stdout),p3=-1;}
template <typename T> inline void write(T x) {
if(p3>(1<<20)) flush();
if(x<0) buf2[++p3]='-',x=-x;
do {a[++p]=x%10+48;} while(x/=10);
do {buf2[++p3]=a[p];} while(--p);
buf2[++p3]='
';
}
template <typename T,typename... Args> inline void write(T x,Args ...args) {
write(x),write(args...);
}
}
using fast_IO :: read;
using fast_IO :: write;
using fast_IO :: flush;
int n,k,m,p;
int qpow(int a,int x) {
int res=1;
for(;x;x>>=1,a=a*a%p) if(x&1) res=res*a%p;
return res;
}
signed main() {
read(n,k,m,p);n%=p;
write(((qpow(m,k-1)*n%p-m*(m+1)/2%p*qpow(m,k-2)%p*(k-1)%p)%p+p)%p);
flush();
return 0;
}