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;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

int64_t power(int64_t x,int64_t y,int64_t mod){
	int64_t result=1;
	while(y>0){
		if(y&1) result=result*x%mod;
		x=x*x%mod;
        y>>=1;
	}
	return result;
}


void solve(){
    int d,s,mod=1e9+7,sum=0;
    cin >> d;
    vector<int> l(d);
    rep(i,0,d){
        cin >> l[i];
        sum+=l[i];
    }
    cin >> s;

    auto f=[&](int x){
        return power(x,d,mod);
    };

    static int dp[300][2][90001];
    rep(i,0,300) rep(j,0,2) rep(k,0,90001) dp[i][j][k]=-1;
    function<int(int,int,int)> rec=[&](int i,int c,int k){
        if(dp[i][c][k]!=-1) return dp[i][c][k];
        dp[i][c][k]=0;
        if(i==d-1){
            if(c==1){
                dp[i][c][k]=(-f(k)+mod)%mod;
                if(k-l[i]>=0) dp[i][c][k]=(dp[i][c][k]+f(k-l[i])+mod)%mod;
            }else{
                dp[i][c][k]=(f(k)+mod)%mod;
                if(k-l[i]>=0) dp[i][c][k]=(dp[i][c][k]-f(k-l[i])+mod)%mod;
            }
            return dp[i][c][k];
        }
        dp[i][c][k]=rec(i+1,c,k);
        if(k-l[i]>=0) dp[i][c][k]=(dp[i][c][k]+rec(i+1,(c+1)%2,k-l[i]))%mod;
        return dp[i][c][k];
    };
    cout << rec(0,0,s) << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}