초직육면체

시간 제한2초메모리 제한512 MB

요약

변 길이가 l_i인 d차원 직육면체에서 x1+...+xd<=s인 부분의 체적 V에 대해 d!V를 구합니다.

난이도: 어려움10점 중 10점
유형: 수학, 분할 정복, 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

Snuke는 생일 선물로 크기가 $l_1 \times \cdots \times l_d$ 인 $d$ 차원 초직육면체를 받았다. Snuke는 이 도형을 $i$ 번째 좌표가 $0$ 과 $l_i$ 사이에 오도록 놓고, $x_1 + \cdots + x_d \le s$ 를 만족하는 부분을 먹었다. ( $x_i$ 는 $i$ 번째 좌표이다.) Snuke가 먹은 부분의 부피를 $V$ 라 하자. $d!V$ 는 항상 정수임을 증명할 수 있다. $d!V$ 를 $10^9 + 7$ 로 나눈 나머지를 구하라.

입력

첫째 줄에 정수 $d$ 가 주어진다. ( $2 \le d \le 300$ ) 이어서 $d$ 개의 줄이 주어지며, $i$ 번째 줄에 정수 $l_i$ 가 주어진다. ( $1 \le l_i \le 300$ ) 마지막 줄에 정수 $s$ 가 주어진다. ( $0 \le s \le \sum l_i$ )

출력

$d!V$ 를 $10^9 + 7$ 로 나눈 나머지를 출력하라.

힌트

예제 1의 그림:

예제2

예제 1
입력
```
2
6
3
4
```
예상 출력
```
15
```
예제 2
입력
```
5
12
34
56
78
90
123
```
예상 출력
```
433127538
```