Shil has an array of N elements A₁ , A₂ .... A_N . He wants to perform two types of operations on this array.

• 1 i K: Update the value of A_i to K i.e do A_i = K
• 2 P : Find the magical value of subarray A₁, A₂ .... A_P

The magical value of array B₁ , B₂ .... B_r is defined as product of (f[i]+1)^(f[i]+1) where f[i] is the number of times i occurs in array B.

Input:
First line of input contains N and Q denoting length of array A and number of operations to be performed respectively. Next Q lines consists of operations of type 1 or type 2 in the format mentioned above. Each element of array is initially initialized to 0.

Output:
For each operation of type 2 , output the magical value modulo 10⁹ + 7.

Constraints:

• 1 ≤ N ≤ 2 * 10⁵
• 1 ≤ Q ≤ 2 * 10⁵
• 1 ≤ P, K ≤ N