题目描述

Farmer John wrote down $N (1 \le N \le 300)$ digits on pieces of paper. For each $i \in [1,N]$, the ith piece of paper contains 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 would like you to answer $Q (1 \le Q \le 5⋅10^4)$ queries. For the $i$-th query, the cows will move left to right across papers $l_i \cdots r_i (1 \le l_i \le r_i \le N)$, maintaining an initially empty pile of papers. For each paper, they will either add it to the top of the pile, to the bottom of the pile, or neither. In the end, they will read the papers in the pile from top to bottom, forming an integer. Over all $3 ^ {r_i−l_i+1}$ ways for the cows to make choices during this process, count the number of ways that result in the cows reading an integer in $[A,B]$ inclusive, and output this number modulo $10^9+7$.

输入格式

The first line contains three space-separated integers $N, A$, and $B$.

The second line contains $N$ space-separated digits $a_1,a_2, \cdots ,a_N$.

The third line contains an integer $Q$, the number of queries.

The next $Q$ lines each contain two space-separated integers $l_i$ and $r_i$.

输出格式

For each query, a single line containing the answer.

题目大意

给定长度为 $n(1\leq n\leq 300)$ 的整数序列 $a(1\leq a_i\leq 9)$，和整数区间 $[A,B](1\leq A\leq B\leq 10^{18})$，有 $q$ 次询问，每次询问给出 $l,r$。每次询问开始，你有一个空串 $x$，你可以正序对 $a_{l\sim r}$ 进行操作，操作有三种：$x\rightarrow\overline{x+a_i}$，$x\rightarrow\overline{a_i+x}$，或者什么也不做，求 $\overline{x}$ 的取值在 $[A,B]$ 的不同的操作方案数，对 $10^9+7$ 取模。

5 13 327
1 2 3 4 5
3
1 2
1 3
2 5

2
18
34

提示

Explanation for Sample 1

For the first query, there are nine ways Bessie can stack papers when reading the interval $[1,2]$:

• Bessie can ignore $1$ then ignore $2$, getting $0$.
• Bessie can ignore $1$ then add $2$ to the top of the stack, getting $2$.
• Bessie can ignore $1$ then add $2$ to the bottom of the stack, getting $2$.
• Bessie can add $1$ to the top of the stack then ignore $2$, getting $1$.
• Bessie can add $1$ to the top of the stack then add $2$ to the top of the stack, getting $21$.
• Bessie can add $1$ to the top of the stack then add $2$ to the bottom of the stack, getting $12$.
• Bessie can add $1$ to the bottom of the stack then ignore $2$, getting $1$.
• Bessie can add $1$ to the bottom of the stack then add $2$ to the top of the stack, getting $21$.
• Bessie can add $1$ to the bottom of the stack then add $2$ to the bottom of the stack, getting $12$.

Only the $2$ ways that give $21$ yield a number between $13$ and $327$, so the answer is $2$.

SCORING

• Inputs $2-3$: $B<100$
• Inputs $4-5$: $A=B$
• Inputs $6-13$: No additional constraints.