Time Limit: 1.0 s

Memory Limit: 256.0 MB

In the enchanted realm of Arithmia, there is a guardian named Lyra, a wise and skilled protector entrusted with the secrets of the Grand Library. Lyra watches over a mystical shelf holding exactly \(N\) magical books, each with a unique power level represented by an integer. These power levels are stored in an array \(A\), ordered from left to right.

One day, the head librarian assigns Lyra an important mission: to decode hidden patterns within the magical sub-sequences of books within specific sections of the shelf. To do this, Lyra receives \(Q\) queries, each asking for a count of sub-sequences within a certain range of books, specified by their indices. There are two types of queries:

• Type \(1\) (0 L R): Find the number of sub-sequences in the specified range where the sum of power levels is even.
• Type \(2\) (1 L R): Find the number of sub-sequences in the specified range where the sum of power levels is odd.

Since magic calculations can yield enormous numbers, Lyra must return each result modulo \({10^9 + 7}\) to keep them manageable. Your task is to assist Lyra in solving each query efficiently, unlocking the magical patterns hidden within the library’s books.

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, three integers \(type\), \(L (1 \leq L \leq N)\) and \(R (L \leq R \leq N)\) describing each query.

Output

For each query. print the answer modulo  \(10^9+7\) in a new line.

Sample

5 5
9 5 3 5 7
1 1 3
0 1 4
1 4 4
0 5 5
0 3 5

4
7
1
0
3