Micro and Mike are doing some research on arrays. For experiment purpose, they purchased an array A having N integers. They have a board which displays Health of their array.
Health of an array is defined as sum of fitness-factor for all possible non-empty sub-sequences of the array. Fitness-factor of a non-empty sub-sequence is defined as product of maximum and minimum element present in the sub-sequence.
An array P is called subsequence of another array Q, if P can be obtained by deleting zero or more elements of Q.
They want the value on the board to get updated each time they change any element of the array. They've written a program for it. Their program takes the array as input, then allows them to perform Q operations. Each operation is defined as:
xv: Change A[x] to v.
After each operation their program prints the Health of the new array. But they are not sure that their program is correct. So, they want you to write a program that performs the same task, so that they can compare their output against yours.
Input:
First line consists of two space separated integers denoting N and Q.
Second line consists of N space separated integers denoting the array A.
Each of the following Q lines consists of a single operation as defined.
Output:
After performing each operation print the health of the new array in a new line. Since output can be large, print it modulo 109+7.
Constraints:
1≤N≤105
1≤Q≤2×105
1≤A[i],v≤109
1≤x≤N
After performing 1st operation array will be [1,4,3]. All possible sub-sequences along with their fitness factor are:
1 - 1
4 - 16
3 - 9
[1,4] - 4
[1,3] - 3
[4,3] - 12
[1,4,3] - 4
Now, health of the array is sum of fitness factor of all sub-sequences which is 49.
After performing 2nd operation array will be [3,4,3]. All possible sub-sequences along with their fitness factor are:
3 - 9
4 - 16
3 - 9
[3,4] - 12
[3,3] - 9
[4,3] - 12
[3,4,3] - 12
Now, health of the array is sum of fitness factor of all sub-sequences which is 79.
