Sunuke received a d-dimensional hypercube with a side length of l1 × ... × ld as a birthday present. Sunuke placed this rectangular parallelepiped so that the range of the i-th coordinate was 0 or more and li or less, and ate the part that satisfied x1 + ... + xd ≤ s. However, xi represents the i-th coordinate. If the volume of the part eaten by Sunuke is V, it can be proved that d! V (V multiplied by the factorial of d) is an integer. Find the remainder of d! V divided by 1,000,000,007.

Constraints

* 2 ≤ d ≤ 300
* 1 ≤ li ≤ 300
* 0 ≤ s ≤ $ \ sum l_ {i} $
* All inputs are integers

Input


d
l1
.. ..
ld
s


Output

Output d! V divided by 1,000,000,007.

Examples

Input

2
6
3
4


Output

15


Input

5
12
34
56
78
90
123


Output

433127538
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename T,T MOD = 1000000007>
struct Mint{
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }
  
  Mint inv(){return pow(MOD-2);}
  
  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}
  
  Mint operator+(Mint a) const{return Mint(v)+=a;};
  Mint operator-(Mint a) const{return Mint(v)-=a;};
  Mint operator*(Mint a) const{return Mint(v)*=a;};
  Mint operator/(Mint a) const{return Mint(v)/=a;};

  Mint operator-(){return v?MOD-v:v;}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}
  bool operator <(const Mint a)const{return v <a.v;}
};

//INSERT ABOVE HERE
using M = Mint<int>;
const int MAX = 303*303;
M dp[2][MAX];
M nx[2][MAX];
signed main(){
  int n;
  cin>>n;
  vector<int> l(n);
  for(int i=0;i<n;i++) cin>>l[i];

  int s;
  cin>>s;

  dp[0][0]=1;
  for(int i=0;i<n;i++){
    for(int j=0;j<MAX;j++) nx[0][j]=nx[1][j]=M(0);

    for(int j=0;j<MAX;j++){
      nx[0][j]+=dp[0][j];
      nx[1][j]+=dp[1][j];

      if(j+l[i]>=MAX) continue;
      
      nx[1][j+l[i]]+=dp[0][j];
      nx[0][j+l[i]]+=dp[1][j];
    }    

    for(int j=0;j<MAX;j++) dp[0][j]=nx[0][j];
    for(int j=0;j<MAX;j++) dp[1][j]=nx[1][j];
  }
  
  M ans(0);
  for(int x=0;x<=s;x++)
    ans+=(dp[0][x]-dp[1][x])*M(s-x).pow(n);
  
  cout<<ans.v<<endl;
  return 0;
}

