As the newly-promoted manager of a casino, Bob is attempting to make a new type of random number generator!

This number generator will generate an arbitrary integer between \(0\) and \(6\) inclusive. Here is how the generator works:

First, the generator will be given an array \(A\) with \(N\) nonnegative integers, where \(0 \le A_i \le 10^9\) for all \(1 \le i \le N\).

Next, to generate a number, the generator will concatenate the integers in the subarray of a range \([L, R]\).

Finally, the outputted random integer will be equal to the remainder of the concatenated integer when divided by \(7\) (in other words, it is equal to the integer modulo \(7\)).

Since this is a casino, many queries will be done and Bob does not know how to do this efficiently. As an intern, can you please help Bob with his random number generator?

For this problem, Python users should submit their submissions in PyPy over CPython.

Input Specification

The first line contains two integers \(N\) and \(Q\) \((1 \le N, Q \le 2 \times 10^5)\), representing the size of the array and the number of queries.

The next line contains \(N\) integers separated by spaces, with the \(i\)-th integer representing the element in the \(i\)-th element in the array.

Each of the following \(Q\) lines contains two integers \(L\) and \(R\) \((1 \le L \le R \le N)\), representing the subarray range of the query.

Output Specification

Output \(Q\) lines, with the \(i\)-th line representing the concatenation of the integers in the subarray, modulo \(7\).

Subtasks

Note that you will not be required to pass the sample input to receive points for the subtasks. Additionally, you will not be required to pass subtask 1 in order to get points on subtask 2.

Subtask 1 [10%]

\(1 \le N, Q \le 100\)

Subtask 2 [30%]

The elements in the array will either be \(0\) or \(1\).

Subtask 3 [60%]

No additional constraints.

Sample Input

5 2
1 23 2 0 0
1 3
2 5

Sample Output

0
2

Sample Explanation

The first query's concatenation is \(1232\), which is a multiple of \(7\). The answer for the first query is thus \(0\).

The second query's concatenation is \(23200\), which has a remainder of \(2\) when divided by \(7\). The answer for the second query is thus \(2\).