시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 47 | 24 | 19 | 48.718% |
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.
2 6 3 4
15
5 12 34 56 78 90 123
433127538
Illustration to Sample 1: