解法：
1.首先，看到有限制的只有15个，因此可以用容斥原理：

ans=全部没有限制的方案-有一个超过限制的方案数+有两个超过限制的方案数-有三个超过限制的方案数….

2.把m组无限制的数中选n个的方案数：C(n+m-1,n)。就是隔板法公式，简单证明：

xi为选xi个第i组数，这个问题相当于求x1+x2+x3+..+xm=n，求x解集的方案数，也就是有n个1，用m-1个0

将他们分隔开的方案数，也就是C(n+m-1,n)

有一个超过限制直接用总数减去（这个的限制+1)就是当前的总数，相当于强制要选限制+1个，其他任意。。。

注意本题是要求不超过m的方案数，也就是C(n+0-1,0)+C(n+1-1,1)+C(n+2-1,2)+…+C(n+m-

1,m)=C(n+m,m)

(因为C(n,m)=C(n-1,m-1)+C(n-1,m))

3.最后由于M，N太大，不能直接算组合数，所以用lucas定理来求

数据不大，我没有线性预处理逆元。

//BZOJ 1272 Lucas + 容斥 + 隔板法

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100005;
int n, k, m, mod, b[20];
LL fac[maxn], ans = 0;
LL powmod(LL a, LL n){
    LL res = 1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
void init(){
    fac[0]=1LL;
    for(int i=1;i<=mod;i++){
        fac[i]=fac[i-1]*i%mod;
    }
}
LL C(LL n, LL m){
    if(m>n) return 0;
    return fac[n]*powmod(fac[m]*fac[n-m]%mod,mod-2)%mod;
}
LL Lucas(LL n, LL m){
    if(m == 0) return 1;
    return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}
void dfs(int now, int x, int w){
    if(now==k+1){
        ans = (ans + x*Lucas(n+m-w,m-w))%mod;
        return;
    }
    dfs(now+1,-x,w+b[now]+1);
    dfs(now+1,x,w);
}
int main()
{
    scanf("%d%d%d%d",&n,&k,&m,&mod);
    for(int i=1; i<=k; i++) scanf("%d",&b[i]);
    init();
    dfs(1,1,0);
    printf("%lld\n", (ans%mod+mod)%mod);
    return 0;
}