Odd Query

CLown1331 National Girls' Programmi...
Limits 1s, 128 MB

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

For example, 1,2,41, 2, 4 is a subsequence of 1,2,2,4,3,61, 2, 2, 4, 3, 6, while 4,2,14, 2, 1 is not.

Alice is given a sequence of nn numbers A1,A2,,AnA_1, A_2, \dots, A_n.

She wants to perform qq operations on the sequence.

  • XVX \, \, V, change the value of the element at the index XX to VV. That means, AX=VA_X = V.

  • After changing the value, she also wants to calculate the number of sub-sequence with an odd sum.

As she is feeling lazy, she doesn't want to do the calculation by herself. So help her by doing the calculation for her.

As the answer can be quite big, print the answer modulo 109+710^9+7. In other words, divide the answer by 109+710^9 + 7 and print the remainder after the division.

Input

The first line contains two integers nn and q(1n,q105)q ( 1 \leq n, q \leq 10^5 ).

The next line will contain nn integers, A1,A2,,An(1Ai109;1iN)A_1, A_2, \dots, A_n (1 \leq A_i \leq 10^9; 1\leq i \leq N).

Each of the next qq lines will contain, two integers X(1XN)X (1 \leq X \leq N) and V(1V109)V (1 \leq V \leq 10^9) describing each query.

Output

For each operation. print the answer modulo 109+710^9+7 in a new line.

Samples

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

Submit

Login to submit.

Statistics

70% Solution Ratio
Carmel.338175Earliest, 8M ago
prodip_bsmrstuFastest, 0.0s
mobarak_aiubLightest, 1.5 MB
serotoninShortest, 447B
Toph uses cookies. By continuing you agree to our Cookie Policy.