Given an array of
integers, support
queries of the following type:
l r
return the number of subsequences between indexl
tor
(inclusive) which have an even sum.
As the results of these queries may be extremely large, output them modulo .
A subsequence can be created from by deleting some elements (possibly none, but not all). Two subsequences are different if one contains an index from the original array that the other does not have.
Constraints
For all subtasks:
Points Awarded | Additional Constraints |
---|---|
3 points | All |
5 points | |
7 points | No further constraints |
Input Specification
The first line contains two space-separated integers and
.
The next line contains space-separated integers — the array
.
The next lines each contain two space-separated integers
, and
, denoting the
query.
Output Specification
Output the answer to each query in order on separate lines.
Sample Input
6 1
4 3 1 2 5 7
2 4
Sample Output
3
Comments