Odd Query

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, 4$ is a subsequence of $1, 2, 2, 4, 3, 6$, while $4, 2, 1$ is not.

Alice is given a sequence of $n$ numbers $A_1, A_2, \dots, A_n$.

She wants to perform $q$ operations on the sequence.

• $X \, \, V$, change the value of the element at the index $X$ to $V$. That means, $A_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 $10^9+7$. In other words, divide the answer by $10^9 + 7$ and print the remainder after the division.

Input

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

The next line will contain $n$ integers, $A_1, A_2, \dots, A_n (1 \leq A_i \leq 10^9; 1\leq i \leq N)$.

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

Output

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

Samples

Input	Output
3 1 5 3 3 2 4	4

Input	Output
1 1 3 1 2	0