You are given an array \(A\) of \(N\) integers. 

Also, you are given \(Q\) queries of the following type:

• \(1 \ x \ v\): Change the value of the element at \(x^{th}\) index to \(v\) i.e. set \(A[x] = v\).
• \(2 \ l \ r\): Determine the number of pairs \((i,j)\) such that:
  • \(l \le i < j \le r\)
  • \(A[i] \times A[j]\)is minimum possible among all such possible pairs of elements

Your task is to determine the sum of answers for queries of Type \(2\) over all \(Q\) queries.

Note

• Assume \(1\)-based indexing.
• The sum can be very large, print the output in modulo \(10^9 + 7\). 

Input format

• The first line contains an integer \(T\) that denotes the number of test cases.
• For each test case:
  • The first line contains two space-separated integers that denotes \(N \ Q\).
  • The next line contains \(N\) space-separated integers that denotes the array \(A\).
  • The next \(Q\) lines contain queries.

Output format

For each test case, print an integer denoting the sum of the answer for all the queries of Type \(2\) in a new line.

Constraints

\(1 \le T \le 10 \\ 1 \le N, Q \le 10^5 \\ 1 \le l < r \le N \\ 1 \le x \le N \\ 1 \le v, A[i] \le 10^6\)