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

Constraints

• 2 ≤ d ≤ 300
• 1 ≤ l_i ≤ 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

---