16846번 - Hyperrectangle 다국어

문제

Snuke received a d-dimensional hyperrectangle of size l₁ × · · · × l_d as a birthday present. Snuke placed it such that its i-th coordinate becomes between 0 and l_i, and ate the part of the hyperrectangle that satisfies x₁ + · · · + x_d ≤ s. (Here x_i 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 10⁹ + 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 l_i (1 ≤ l_i ≤ 300). Last line contains one integer s (0 ≤ s ≤ Σl_i).

출력

Print d!V modulo 10⁹ + 7.

제한

힌트

Illustration to Sample 1: