Hyperrectangle

Time limit2sMemory limit512 MB

Summary

Compute d!V for the volume of a box with side lengths li where sum xi <= s via characteristic polynomials and Lenstra inclusion of capped orthants.

Level: Hard10 of 10
Topics: Math, Divide and conquer, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

Snuke received a $d$ -dimensional hyperrectangle of size $l_1 \times \cdots \times l_d$ as a birthday present. Snuke placed it so that its $i$ -th coordinate lies between $0$ and $l_i$ , and ate the part of the hyperrectangle satisfying $x_1 + \cdots + x_d \le s$ . (Here $x_i$ denotes the $i$ -th coordinate.) Let $V$ be the volume of the part Snuke ate. We can prove that $d!V$ is always an integer. Compute $d!V$ modulo $10^9 + 7$ .

Input

The first line contains one integer $d$ ( $2 \le d \le 300$ ). Then $d$ lines follow; the $i$ -th of these lines contains one integer $l_i$ ( $1 \le l_i \le 300$ ). The last line contains one integer $s$ ( $0 \le s \le \sum l_i$ ).

Output

Print $d!V$ modulo $10^9 + 7$ .

Hint

Illustration for Sample 1:

Examples2

Example 1
Input
```
2
6
3
4
```
Expected output
```
15
```
Example 2
Input
```
5
12
34
56
78
90
123
```
Expected output
```
433127538
```