This problem is worth 70% of the 100 points allocated to S5

Consider an array of length ~N~, filled with positive integers from the range ~1~ to ~N~, inclusive (the array does not necessarily need to contain every number, however).

An array with maximum element ~x_i~ is considered happy under the following conditions:

1. All of its elements lie in the range ~1~ to ~x_i~
2. Each number from the range ~1~ to ~x_i~ occur at least once in the array
3. The first occurence of the positive integer ~i (1 \leq i < x_i)~ lies before the first occurence of the positive integer ~i+1~.

Brian hands you over a happy array, and wants you to find the number of happy arrays of the same length that are lexographically less than or equal to the happy array modulo ~10^9 + 7~. However, he thinks this current task is too easy for you. Instead, he wants you to find this result for ~Q~ queries, where each query ~q_i~ increases the element ~i~ in the original happy array by ~1~. If the modified happy array is no longer happy, then output -1 for that query. After each query, the change in element ~i~ resets if ~b_i = 0~, otherwise it will persist.

Input Specification

The first line of input will contain two space-separated integers ~N, Q~, representing the number of elements in the array and the number of queries, respectively.

The second line of input will contain ~N~ space-separated integers ~a_i~, representing the elements in the original happy array. It is guaranteed that this array satisifies the happy condition.

The next ~Q~ lines of input will contain two integers ~q_i, b_i~ each, representing the query to increase element ~i~ by 1 and whether to persist the query or not (~1~ means persist, ~0~ means discard). It is guaranteed that if a query were to persist, then the array is still happy.

Output Specification

Output ~Q~ lines, each containing one integer, representing the number of happy arrays lexographically less than or equal to the new array. Since the answer may be very large, output modulo ~10^9 + 7~.

Constraints

For all subtasks, ~b_i \in \{0,1\}~

Marks Allocated	Bounds on ~N~	Bounds on ~Q~	Bounds on ~a_i~
~5\%~	~N = 3~	~Q = 1~	~a_i \in \{1, 2, 3\}~
~20\%~	~1 \leq N \leq 50~	~1 \leq Q \leq 10~	~1 \leq a_i \leq N~
~5\%~	~1 \leq N \leq 2 \times 10^3~	~Q = 1~	~a_i \in \{1, 2\}~
~50\%~	~1 \leq N \leq 5 \times 10^3~	~1 \leq Q \leq 50~	~1 \leq a_i \leq N~
~20\%~	~1 \leq N \leq 5 \times 10^3~	~1 \leq Q \leq 10^4~	~1 \leq a_i \leq N~

Sample Input 1

4 2
1 1 2 2
4 0
3 0

Sample Output 1

5
-1

Sample Explanation 1

There are two queries, neither of which persist. The first query changes the array to 1 1 2 3, which is still happy. There are 5 happy arrays that are lexographically less than or equal to this array, those being 1 1 1 1, 1 1 1 2, 1 1 2 1, 1 1 2 2, 1 1 2 3. Keep in mind that 1 1 1 3 does NOT satisfy all conditions to be a happy array.

The second query changes the array to 1 1 3 2, which is not a happy array.

Sample Input 2

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

Sample Output 2

33
45
-1