#include<cstdio>#include<cstring>#include<cstdlib>#include<ctime>#include<algorithm>#include<iostream>#include<string>#include<cmath>#include<queue>#include<vector>#include<map>using namespace std;int a[2005];int c[2005][120];int n=105, M;inline int lowbit(int i){return i&(-i); }void Add(int C[], int k, int val){ for (int i=k; i<=n; i+=lowbit(i)) C[i] = (C[i]+val)%M;}int getSum(int C[], int k){ int res=0; for (int i=k; i>0; i-=lowbit(i)) res = (res+C[i])%M; return res;}int main(){ int N, K, P, i, j, k, p, q, bg, ed, tmp; while (scanf ("%d%d%d%d", &N, &K, &P, &M)!=EOF) { if (K==0) K=1; for (i=1; i<=N; i++) scanf ("%d", a+i); for (i=1; i<=N; i++) a[i]++; memset (c, 0, sizeof(c)); Add(c[1], a[1], 1); for (i=2; i<=N; i++) { bg = max(0, a[i]-P-1); ed = min(n, a[i]+P); if (bg>=ed) { Add(c[1], a[i], 1); continue; } int ttmp = ((getSum(c[K], ed) - getSum(c[K], bg))%M + M)%M; for (k=K-1; k>=1; k--) { tmp = ((getSum(c[k], ed) - getSum(c[k], bg))%M + M)%M; Add(c[k+1], a[i], tmp); } Add(c[K], a[i], ttmp); Add(c[1], a[i], 1); } int ans=getSum(c[K], n); printf ("%dn", ans); } return 0;}
