Migrated from Lutece 1310 Dynamic Dynamic Programming

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is a common formula of dynamic programming:

Now let's make it more dynamic. You will be given the $c_j$ for $1\leq j\leq n$ initially, then there are two types of query:

1. Change $c_j$ to $v$.

2. Return the value of $dp_{i,j}$.

It is guaranteed that $1\leq j\leq n$ for all $j$ above.

Input

the first line contains two integers $n$ and $m$: the length of the array $c$ and the number of queries.

There are $n$ integers in next line. The $j^{th}$ integer indicates $c_j$.

Then $m$ lines is following, each with a query. There are two types of query:

1 j v: Change $c_j$ to $v$.

2 i j: Return the value of $dp_{i,j}$.

$1\leq n, m\leq 10^5$

$0\leq c_j, v\leq 10^9$

$0\leq i\leq 20$

$1\leq j \leq n$

Output

For each query 2 i j, output the answer in one line. As the answer may be too large, output it modulo $(10^9+7)$ (i.e. if the answer is $X$, you should output $X\ \%\ (10^9+7)$).

Samples

3 4
1 2 3
2 1 2
2 2 3
1 1 2
2 2 3

3
10
13

Resources

The 14th UESTC Programming Contest Final