#include #define rep(i,n) for(int i=0;i<(int)(n);i++) #define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++) #define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++) #define setp(n) fixed << setprecision(n) template bool chmax(T &a, const T &b) { if (a bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } #define ll long long #define vll vector #define vi vector #define pll pair #define pi pair #define all(a) (a.begin()),(a.end()) #define rall(a) (a.rbegin()),(a.rend()) #define fi first #define se second #define pb push_back #define ins insert #define debug(a) cerr<<(a)< ostream &operator<<(ostream &os, const pair &p){return os<<"("< istream &operator>>(istream &is, pair &p){return is>>p.fi>>p.se;} //------------------------------------------------- //--ModInt //------------------------------------------------- constexpr uint_fast64_t MOD = 1e9+7; class mint { private: using Value = uint_fast64_t; Value n; public: mint():n(0){} mint(int_fast64_t _n):n(_n<0 ? MOD-(-_n)%MOD : _n%MOD){} mint(const mint &m):n(m.n){} friend ostream& operator<<(ostream &os, const mint &a){ return os << a.n; } friend istream& operator>>(istream &is, mint &a){ Value temp; is>>temp; a = mint(temp); return is; } mint& operator+=(const mint &m){n+=m.n; n=(n>=1; } return ret; } mint inv() const {return pow(MOD-2);} }; //------------------------------------------------- //--Combination (depends on ModInt) //------------------------------------------------- class Combination { private: ::std::vector _fact; ::std::vector _finv; public: Combination(int n):_fact(n+1), _finv(n+1){ _fact[0] = _fact[1] = 1; _finv[0] = _finv[1] = 1; for(int i=2; i<=n; i++){ _fact[i] = _fact[i-1]*i; _finv[i] = _fact[i].inv(); } } mint fact(int x){return _fact[x];} mint finv(int x){return _finv[x];} mint comb(int x, int y){ if (y>x || y<0) return 0; return _fact[x]*_finv[y]*_finv[x-y]; } mint homo(int x, int y){return comb(x+y-1, y);} }; //------------------------------------------------- constexpr int N_MAX = 40; constexpr int M_MAX = 20000; mint dp[N_MAX+1][N_MAX+1][M_MAX+1]; mint sum[N_MAX+1][N_MAX+1][M_MAX+2]; int main(void) { cin.tie(0); ios::sync_with_stdio(false); int N,Mp,Mq,L; cin>>N>>Mp>>Mq>>L; Combination bn(2*M_MAX); vi S(N); rep(i,N) cin>>S[i]; dp[0][0][0]=1; rep(i,N)FOR(j,0,N){ FOR(k,0,Mq){ sum[i][j][k+1] = sum[i][j][k]+dp[i][j][k]; } FOR(k,0,Mq){ dp[i+1][j][k] = dp[i][j][k]; if (j>0){ dp[i+1][j][k] += sum[i][j-1][k]-sum[i][j-1][max(0,k-S[i])]; } } } mint ans=0; FOR(j,0,N)FOR(k,0,Mq){ int p = Mp-(L*j-k); if (p<0) continue; ans += bn.comb(p+N-1,N-1)*dp[N][j][k]; } cout<