시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 8 7 7 87.500%

문제

Snuke received a d-dimensional hyperrectangle of size l1 × · · · × ld as a birthday present. Snuke placed it such that its i-th coordinate becomes between 0 and li, and ate the part of the hyperrectangle that satisfies x1 + · · · + xd ≤ s. (Here xi denotes the i-th coordinate). Let V be the volume of the part eaten by Snuke. We can prove that d!V (V times the factorial of d) is always an integer. Compute d!V modulo 109 + 7.

입력

First line of the input file contains one integer d (2 ≤ d ≤ 300). Then d lines follow; i-th of these lines contain one integer li (1 ≤ li ≤ 300). Last line contains one integer s (0 ≤ s ≤ Σli).

출력

Print d!V modulo 109 + 7.

예제 입력 1

2
6
3
4

예제 출력 1

15

예제 입력 2

5
12
34
56
78
90
123

예제 출력 2

433127538

힌트

Illustration to Sample 1: