Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

すぬけ君は，誕生日プレゼントとして辺の長さが l1 &times; . . . &times; ld の d 次元超直方体をもらった．すぬけ君は，この直方体を i 番目の座標の範囲が 0 以上 li 以下となるようにおき，x1 + . . .  + xd ≤ s をみたす部分を食べてしまった．ただし xi は i 番目の座標を表す．すぬけ君の食べた部分の体積を V とすると，d!V (V に d の階乗をかけた値) は整数となることが証明できる．d!V を1,000,000,007 で割ったあまりを求めよ．

Constraints

 2 ≤ d ≤ 300 

 1 ≤ li ≤ 300

 0 ≤ s ≤ $\sum l_{i}$

 入力は全て整数である

Input

d
l1
. . .
ld
s

Output

d!V を 1,000,000,007 で割ったあまりを出力せよ．

Sample Input 1

2
6
3
4

Sample Output 1

15

Sample Input 2

5
12
34
56
78
90
123

Sample Output 2

433127538



Sample input:
2
6
3
4


Sample output:
15

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    MOD = 10**9 + 7
    D = int(readline())
    L = [int(readline()) for i in range(D)]
    S = int(readline())
    dp = [0]*(S+1)
    dp[S] = 1
    for i in range(D):
        l = L[i]
        for i in range(l, S+1):
            dp[i-l] -= dp[i]
    ans = 0
    for i in range(S+1):
        ans += pow(i, D, MOD) * dp[i]
    ans %= MOD
    write("%d\n" % ans)
solve()