Digit Paper Pile Query

Farmer John wrote down \(N\ (1 \le N \le 300)\) digits on pieces of paper. For each \(i\in[1,N]\), the \(i\)th paper contains a digit \(a_i\ (1 \le a_i \le 9)\). The cows have two favorite integers \(A\) and \(B\) \((1 \le A \le B < 10^{18})\) and they wish to answer \(Q\ (1 \le Q \le 5\cdot10^4)\) queries.

For the \(i\)th query, the cows consider the segment of papers from index \(l_i\) to \(r_i\) (\(1 \le l_i \le r_i \le N\)). They process the papers in order from left to right. Initially, they have an empty pile. For every paper, they can decide to:

• Do nothing; or
• Add the digit to the top of the pile; or
• Add the digit to the bottom of the pile.

After processing all papers in the segment, they read the pile from top to bottom to form an integer. Note that if no paper is chosen the resulting integer is empty and is not counted. Over all \(3^{r_i-l_i+1}\) ways of making choices, count the number of ways that result in an integer \(X\) satisfying \(A \le X \le B\). Output the answer modulo \(10^9+7\).

Note: Since each digit is between 1 and 9, any formed number with more than 19 digits will exceed \(B\) (because \(B < 10^{18}\)). Therefore, you may ignore options that lead to numbers with length more than 19.

inputFormat

The first line contains four space‐separated integers \(N\), \(Q\), \(A\), and \(B\). The second line contains \(N\) space‐separated digits \(a_1, a_2, \ldots, a_N\). Each of the next \(Q\) lines contains two integers \(l_i\) and \(r_i\) representing a query.

outputFormat

For each query, output a single line containing the number of ways (modulo \(10^9+7\)) to form an integer in the range \([A, B]\) from the given segment.

sample

3 2 10 100
1 2 3
1 2
1 3

4
12