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, is a subsequence of , while is not.
Alice is given a sequence of numbers .
She wants to perform operations on the sequence.
, change the value of the element at the index to . That means, .
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 . In other words, divide the answer by and print the remainder after the division.
The first line contains two integers and .
The next line will contain integers, .
Each of the next lines will contain, two integers and describing each query.
For each operation. print the answer modulo in a new line.
3 1 5 3 3 2 4
1 1 3 1 2