G. Olympics Champion
time limit per test
8 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Duckduck is a marathon runner who has qualified for the 2024 Olympics in Paris.

The Olympic Games will start in $$$n$$$ days, and Duckduck needs to practice for his race, so he has decided to train every day from day $$$1$$$ to day $$$n$$$ until the Olympics begin. Each day, Duckduck runs $$$k$$$ kilometers, where the distance $$$k$$$ is chosen randomly and independently from the set $$$\{0, 1, \dots, 12\}$$$. For each $$$k$$$ from $$$0$$$ to $$$12$$$, the probability of running exactly $$$k$$$ kilometers on a single day is given as $$$\frac{p_k}{100}$$$.

As you might expect from his name, Duckduck is not very smart. Duckduck believes he will win the gold medal if the total distance he runs over the $$$n$$$ days is exactly $$$x$$$ kilometers.

Your task is to calculate the probability that the total distance run after $$$n$$$ days is exactly $$$x$$$.

The probability can be expressed as an irreducible fraction $$$\frac{P}{Q}$$$. Since the answer might be large, you should calculate and print the value $$$P \cdot Q^{-1} \pmod{10^9 + 7}$$$, where $$$Q^{-1}$$$ is the modular multiplicative inverse of $$$Q$$$ modulo $$$10^9 + 7$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 100$$$), the number of test cases.

Then $$$T$$$ test cases follow.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le x \le 12 \times n$$$), representing the number of training days and the target total distance, respectively.

The second line of each test case contains $$$13$$$ space-separated integers $$$p_0, p_1, \dots, p_{12}$$$ ($$$0 \le p_i \lt 100$$$), where $$$\frac{p_i}{100}$$$ is the probability of running exactly $$$i$$$ kilometers on any given day.

It is guaranteed that $$$\sum_{i=0}^{12} p_i = 100$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print a single line containing one integer: the probability that the total distance is exactly $$$x$$$ after $$$n$$$ days, calculated as $$$P \cdot Q^{-1} \pmod{10^9 + 7}$$$.

Example
Input
3
10 10
10 10 10 10 10 10 10 10 5 5 5 5 0
5452 28605
14 8 3 9 0 12 12 15 11 2 1 13 0
1092 1628
3 5 2 5 6 16 0 9 9 4 12 14 15
Output
842855833
480768144
714626769