Chung is studying sequence partitioning. He learn that a valid partition as a division of a sequence into one or more contiguous segments such that every element belongs to exactly one segment.

Initially, he has a sequence of ~n~ integers. He calls a partition a ~k~-signature partition if every segment in the partition contains at least one occurrence of the integer ~k~.

Mr. K thinks the static problem is too easy, so he challenges Chung to solve the problem dynamically by processing the following queries:

• ~1 \ l \ r \ v~ (~1 \le l \le r \le n, |v| \le 10^5~) — Add the value ~v~ to every element in the range ~[l, r]~. It is guaranteed that after this operation, all elements ~a_i~ in the sequence satisfy ~1 \le a_i \le 10^5~.

• ~2 \ l \ r \ k~ (~1 \le l \le r \le n, 1 \le k \le 10^5~) — Consider only the subarray from index ~l~ to ~r~. Calculate the number of ~k~-signature partitions for this subarray. Since the answer can be large, output it modulo ~10^9 + 7~.

Overwhelmed by the changing array, Chung asks for your help to answer Mr. K's queries!

Input

The first line contains a positive integer ~T~ (~1 \leq T \leq 10^5~) — the number of test cases. Each test case is described as follows:

The first line contains two positive integers ~n, q~ (~1 \leq n, q \leq 10^5~) — the length of the sequence ~a~ and the number of queries you need to process.

The second line contains ~n~ positive integers ~a_i~ (~1 \leq a_i \leq 10^5~) — the values of the elements in the sequence ~a~.

The next ~Q~ lines describe the queries as stated in the problem.

The data guarantees that the total ~n~ and ~q~ will not exceed ~10^5~.

Output

For each query of type ~2~, return the answer. Since the answer may be large, return the result modulo ~10^9 + 7~.

Sample Input 1

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

Sample Output 1

9
1

Notes

1. One Segment (1 way)

• | 1 | 2 | 1 | 3 | 1 | |:---:|:---:|:---:|:---:|:---:|

2. Two Segments (4 ways)

• | 1 | 2 | 1 | 3 | 1 | |:---:|:---:|:---:|:---:|:---:|

• | 1 | 2 | 1 | 3 | 1 | |:---:|:---:|:---:|:---:|:---:|

• | 1 | 2 | 1 | 3 | 1 | |:---:|:---:|:---:|:---:|:---:|

• | 1 | 2 | 1 | 3 | 1 | |:---:|:---:|:---:|:---:|:---:|

3. Three Segments (4 ways)

• | 1 | 2 | 1 | 3 | 1 | |:---:|:---:|:---:|:---:|:---:|

• | 1 | 2 | 1 | 3 | 1 | |:---:|:---:|:---:|:---:|:---:|

• | 1 | 2 | 1 | 3 | 1 | |:---:|:---:|:---:|:---:|:---:|

• | 1 | 2 | 1 | 3 | 1 | |:---:|:---:|:---:|:---:|:---:|