Bob is going trick-or-treating in an extremely rich neighborhood composed of ~N~ houses arranged in a row. His friends have given him a list of integers ~a_1, a_2, ..., a_N~ which denotes the amount of candy that the ~i~th house gives them.

However, because he is a seasoned trick-or-treater, Bob can get much more candy than that. Bob defines a list ~b_1, b_2, ..., b_N~ which denotes the factor of candy that the ~i~th house will give him. Initially, ~b_i = a_i!~ for all ~i~ (where ~a!~ is the factorial of ~a~).

In his route, Bob will start at a house ~L~ where, using his charm, he will obtain ~b_L~ candies. In addition, he will continue right until a house ~R~, where at each subsequent house he will boast about the amount of candy that he has already collected, causing his candy count to increase by a factor of ~b_i~. Note that if Bob goes from houses ~L~ to ~R~, his total amount of candy at the end will be ~\prod_{i=L}^{R} b_i~.

Bob would like you, his trusted friend, to help him do a few calculations before he starts his route. He will ask you to handle ~Q~ queries, of the following types:

1. 1 i v The ~i~th house has increased its candy supply, meaning that its value of ~b_i~ is increased by a factor of ~v!~.
2. 2 l r Bob considers taking the route from houses ~L~ to ~R~. In order to share the candies with his friends, he would like to know the number of different ways that he can evenly split the number of candies that he collects. Formally, he would like to find the number of positive divisors of ~\prod_{i=L}^{R} b_{i}~, modulo ~10^9 + 7~.

Please help Bob answer these queries so he can have a successful Halloween!

Input Specification

The first line of input will contain two space-separated integers, ~N~ and ~Q~ ~(1 \le N, Q \le 10^5)~.

The next line of input will contain ~N~ space-separated integers, ~a_1, a_2, ..., a_N~ ~(1 \le a_i \le 500)~.

The next ~Q~ lines of input will each contain one query as per the description above ~(1 \le i \le N, 1 \le v \le 500, 1 \le L \le R \le N)~.

Output Specification

For each query of type ~2~, output the answer on a separate line.

Subtasks

Subtask 1 [10%]

~1 \le N, Q \le 100~

~1 \le a_i, v \le 2~

For each query of type ~2~, it is guaranteed that the number of candies will be less than or equal to ~10^{9}~.

Subtask 2 [20%]

~1 \le a_i, v \le 2~

Subtask 3 [70%]

No further constraints.

Sample Input 1

3 2
1 2 3
1 2 2
2 1 3

Sample Output 1

8

Explanation for Sample Output 1

Intially, Bob's list is ~[1, 2, 6]~. After the first operation, it is ~[1, 4, 6]~. For the second operation, the amount of candies is ~1 \cdot 4 \cdot 6 = 24~. Since there are ~8~ ways to evenly distribute ~24~ candies (~24~ can be divided by ~1~, ~2~, ~3~, ~4~, ~6~, ~8~, ~12~, and ~24~), the answer is ~8~.

Sample Input 2

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

Sample Output 2

72
195