Cheerio Contest 2 P5 - Subsequence Queries

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types

Given an array a of N integers, support Q queries of the following type:

l r return the number of subsequences between index l to r (inclusive) which have an even sum.

As the results of these queries may be extremely large, output them modulo 10^9+7.

A subsequence can be created from a 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:

  • 1 \le N, Q, a_i \le 10^6
  • 1 \le l \le r \le N
Points Awarded Additional Constraints
3 points All a_i are even
5 points 1 \le N, Q \le 3 \times 10^3
7 points No further constraints

Input Specification

The first line contains two space-separated integers N and Q.

The next line contains N space-separated integers — the array a.

The next Q lines each contain two space-separated integers l_i, and r_i, denoting the i^{\text{th}} 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



There are no comments at the moment.