Hyperrectangle

時間制限 : 2 sec, メモリ制限 : 262144 KB

すぬけ君は,誕生日プレゼントとして辺の長さが l1 × . . . × ldd 次元超直方体をもらった.すぬけ君は,この直方体を i 番目の座標の範囲が 0 以上 li 以下となるようにおき,x1 + . . . + xd ≤ s をみたす部分を食べてしまった.ただし xii 番目の座標を表す.すぬけ君の食べた部分の体積を V とすると,d!V (Vd の階乗をかけた値) は整数となることが証明できる.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
Hyperrectangle

Sample Input 2

5
12
34
56
78
90
123

Sample Output 2

433127538

Source: ACM-ICPC Japan Alumni Group Summer Camp 2014 , Day 2, Tokyo, Japan, 2014-09-13
http://acm-icpc.aitea.net/
http://jag2014summer-day2.contest.atcoder.jp/