E. Potato War 2
time limit per test
0.8 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
"Sometimes it's tough being the best..."

After quintupling the size of his potato plantation, Technoblade got bored of planting potatoes and decided to buy potatoes, for unknown reasons since he already had a lot of potatoes...

Anyway, he made a list of $$$N$$$ potato stores and saw that the $$$i$$$-th store sells potatoes in packages of $$$b_i$$$ potatoes per package. Now Techno wants to know how many ways he can buy exactly $$$B$$$ potatoes.

As he suspects that store number $$$1$$$ belongs to his rival SquidKid, he wants to buy at most $$$t$$$ packages from store $$$1$$$. He can buy any number of packages from the other stores, including $$$0$$$.

In how many ways can he make this purchase? Two ways are considered different if the number of packages of a store bought in an order is different from the other. Since this number is large, print the answer modulo $$$10^9 + 7$$$.

Input

The first line contains two integers $$$N$$$ and $$$B$$$, $$$1 \leq N \leq 100$$$ and $$$1 \leq B \leq 10^{18}$$$. Followed by a line with $$$N$$$ integers $$$1 \leq b_i \leq 500$$$. It is also guaranteed that $$$\sum_{i=1}^{N} b_i \leq 500$$$.

Finally, follows a integer $$$t$$$, $$$0 \leq t \leq 10^{18}$$$.

Output

Print a single line with an integer $$$X$$$, $$$0 \leq X \lt 10^9+7$$$, the number of ways to buy exactly $$$B$$$ potatoes.

Examples
Input
1 10
1
9
Output
0
Input
2 3
1 1
1000
Output
4
Input
2 3
1 1
0
Output
1
Input
3 1000000000
1 2 3
1000000000
Output
250000003