Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Odd Query

By CLown1331 · 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

Discussion

Statistics


71% Solution Ratio

Carmel.338175Earliest, 1M ago

prodip_bsmrstuFastest, 0.0s

mobarak_aiubLightest, 1.5 MB

serotoninShortest, 447B

Submit

Login to submit

Editorial

Even numbers will only create even numbers when added up. Odd numbers will create even numbers when ...

Toph uses cookies. By continuing you agree to our Cookie Policy.