D. Counting Records
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The Counting Song
Gracie's Corner, Gracie's Corner

Michael's favorite artist, Jackson, has recently started releasing new songs at an unprecedented rate. Michael wants to collect a physical copy of every record this artist releases, but his collection is getting too big. He already knows how many songs the artist releases over the first $$$n$$$ days, and wonders how many records he will have to buy on day $$$k$$$ if he continues to purchase every record.

Michael uses the function $$$f(x)$$$ to estimate the number of records released on day $$$x$$$. Michael already knows $$$f(x)$$$ for $$$1 \leq x \leq n$$$ as mentioned above. To compute future estimates, Michael uses the formula

$$$f(x) = \prod_{i=1}^{n}f(x-i)^{f(i)}$$$.

Given the values of $$$f(x)$$$ for $$$1 \leq x \leq n$$$, help Michael calculate his estimate $$$f(k)$$$, modulo $$$10^9 + 7$$$.

Input

The first line of input contains two space-separated integers, $$$n$$$ ($$$1 \leq n \leq 50$$$) and $$$k$$$ ($$$1 \leq k \leq 10^{18}$$$) — the number of days where we already know how many records were released on that day, and the day we would like to estimate, respectively.

The second line of input contains $$$n$$$ space-separated integers, where the $$$i^\text{th}$$$ number is $$$f(i)$$$ ($$$1 \leq f(i) \leq 10^9$$$) — the number of records purchashed on the $$$i^\text{th}$$$ day.

Output

Print a single integer $$$f(k) \bmod {10^9+7}$$$ — the estimate for the number of records purchased on day $$$k$$$.

Examples
Input
2 3
2 3
Output
72
Input
2 4
2 3
Output
139968