B. Bogo Sort Probability
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Once upon a time, in the realm of Sortingland, there was a peculiar sorting algorithm known as Bogo Sort. This algorithm was notorious for its inefficiency, as it relied on sheer luck to sort an array correctly. Despite its shortcomings, Bogo Sort possessed a fascinating characteristic: it had a small probability of sorting an array correctly in a single iteration.

In this kingdom, you are given an array of $$$N$$$ integers, where $$$N$$$ represents the size of the array. The array elements are initially in a random order. Your task is to determine the probability, represented as a number congruent to $$$P/Q \pmod{(10^9 + 7)}$$$, that the Bogo Sort algorithm will correctly sort the array in a single iteration. Here, $$$P$$$ is the numerator and $$$Q$$$ is the denominator of the probability.

Bogo Sort is a simple yet inefficient algorithm. It works as follows:

1.- Check if the array is sorted. If it is, then the sorting is complete.

2.- If the array is not sorted, randomly shuffle the elements to create a new permutation.

3.- Repeat steps 1 and 2 until the array is sorted.

Additionally, you will be given a series of $$$K$$$ queries, each represented by two integers, $$$A$$$ and $$$B$$$. In each query, you need to update the value at position $$$A$$$ of the array with the value $$$B$$$. After each update, you need to recalculate and output the updated probability of Bogo Sort correctly sorting the array in a single iteration.

Input

The input consists of multiple lines.

The first line contains two integers $$$N$$$ and $$$K$$$ $$$(1 \leq N, K \leq 10^6)$$$, representing the size of the array and the number of queries.

The second line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ $$$(1 \leq a_i \leq 10^9)$$$, representing the initial elements of the array.

The following $$$K$$$ lines contain the queries. Each query consists of two integers $$$A$$$ and $$$B$$$ $$$ (1 \leq A \leq N, 1 \leq B \leq 10^9)$$$, representing the position and the updated value in the array.

Output

Output the initial probability of Bogo Sort correctly sorting the array as a number congruent to $$$P/Q \pmod{(10^9 + 7)}$$$, where $$$P$$$ is the numerator and $$$Q$$$ is the denominator of the probability. After each query, output the updated probability in the same format.

Examples
Input
5 2
3 2 5 4 1
2 1
4 6
Output
808333339
616666671
616666671
Input
4 2
2 7 3 5
1 3
1 7
Output
41666667
83333334
83333334
Input
3 2
1 2 3
2 1
3 1
Output
166666668
333333336
1