Snuke 收到了一份 $d$ 维超矩形作为生日礼物，其大小为 $l_1 \times \dots \times l_d$。Snuke 将其放置在坐标系中，使得第 $i$ 个坐标的范围在 $0$ 到 $l_i$ 之间，并吃掉了超矩形中满足 $x_1 + \dots + x_d \le s$ 的部分（其中 $x_i$ 表示第 $i$ 个坐标）。设 $V$ 为 Snuke 吃掉部分的体积。可以证明 $d!V$（$V$ 乘以 $d$ 的阶乘）总是一个整数。请计算 $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
6
3
4

输出格式 1

15

输入格式 2

5
12
34
56
78
90
123

输出格式 2

433127538

说明

样例 1 的示意图：

样例 1 的示意图：