Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M
Given an array of integers, support queries of the following type:
l rreturn the number of subsequences between index
r(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.
For all subtasks:
|Points Awarded||Additional Constraints|
|3 points||All are even|
|7 points||No further constraints|
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 the answer to each query in order on separate lines.
6 1 4 3 1 2 5 7 2 4