#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define T 15
#define P 100000
using namespace std;
int n,m,t,X,a[T+5],g[1<<T];
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
int Fac[P+5],IFac[P+5];I void Init_Fac()//预处理阶乘和阶乘逆元
{
	RI i;for(Fac[0]=i=1;i^X;++i) Fac[i]=1LL*Fac[i-1]*i%X;
	for(IFac[X-1]=QP(Fac[X-1],X-2),i=X-1;i;--i) IFac[i-1]=1LL*IFac[i]*i%X;
}
I int C(CI x,CI y)//卢卡斯定理计算组合数
{
	return x>=y?(x>=X?1LL*C(x/X,y/X)*C(x%X,y%X)%X:1LL*Fac[x]*IFac[y]%X*IFac[x-y]%X):0;
}
I int Calc(CI s)//求强制集合s中的超级宝具超出限制的方案数
{
	RI i,k=m;for(i=1;i<=t;++i) s>>i-1&1&&(k-=a[i]+1);return C(k+n,n);//先选出必选部分，然后所有宝具都可任选
}
int main()
{
	RI i;for(scanf("%d%d%d%d",&n,&t,&m,&X),Init_Fac(),i=1;i<=t;++i) scanf("%d",a+i);
	RI res=0,l=1<<t;for(i=0;i^l;++i) res=(((g[i]=g[i>>1]^(i&1))?X-1LL:1LL)*Calc(i)+res)%X;//经典容斥
	return printf("%d\n",res),0;
}