E. Elevator
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Pep is late for his competitive programming lecture. His building has $$$n + 1$$$ floors, and he lives on the floor $$$n + 1$$$. To go to college, he calls the elevator to his floor. Since he's superstitious, if the elevator stops on more than one floor besides the one it was on when he called and his floor, $$$n + 1$$$, he believes the day will be bad and goes back to bed.

While the elevator is moving, each floor $$$i$$$ has a probability $$$p_i$$$ that the neighbor on floor $$$i$$$ will call the elevator at that moment, causing it to stop. Fortunately for Pep, his neighbors are not obsessed with constantly calling the elevator, that is, $$$p_i \lt 100\%$$$ for $$$1 \le i \le n$$$.

During the college semester, his neighbors may move out, and new neighbors may arrive, changing the probability $$$p_i$$$ of floor $$$i$$$. Pep would also like to make queries to determine the probability of going to class, given that the elevator would be on floor $$$x$$$ when he calls it.

Input

The first line consists of two integers $$$n$$$ $$$(3\le n \le 2\cdot 10^5)$$$ and $$$q$$$ $$$(1\le q \le 2\cdot 10^5)$$$.

The second line consists of $$$n$$$ integers $$$p_i$$$ $$$(0 \le p_i \lt 100)$$$, representing the probability (in percentage) that the elevator will stop on floor $$$i$$$ while in motion.

The next $$$q$$$ lines correspond to queries of two types:

$$$\bullet$$$ $$$1$$$ $$$x$$$ $$$p$$$: Change the probability of floor $$$x$$$, updating $$$p_x$$$ to $$$p$$$.

$$$\bullet$$$ $$$2$$$ $$$x$$$: Answer with the probability that Pep will go to class, given that the elevator is on floor $$$x$$$ when he calls it.

Output

For each query of type $$$2$$$, output a line with the queried probability. We can prove that this probability can be expressed as an irreducible fraction $$$\frac{p}{q}$$$. Print $$$p \cdot q^{-1}$$$ modulo $$$(10^9 + 7)$$$.

Examples
Input
3 1
10 50 50
2 1
Output
750000006
Input
5 1
25 25 0 0 0
2 2
Output
1
Input
4 3
40 50 99 99
2 2
1 3 0
2 2
Output
854300006
1
Note

In Sample 1:

The probability of not stopping on floors $$$2$$$ and $$$3$$$ is $$$\frac{1}{4}$$$.

The probability of stopping only on floor $$$2$$$ is $$$\frac{1}{4}$$$.

The probability of stopping only on floor $$$3$$$ is $$$\frac{1}{4}$$$.

Thus, the final answer is $$$\frac{3}{4}$$$.