Piling Papers

【题目描述】

有 $N$ 张纸，编号 $1 \sim N$。

每张纸上都写有一个一位数字，其中第 $i$ 张纸上写有数字 $a_i$。

给定一个整数区间 $[A,B]$，请你回答 $Q$ 个询问。

对于第 $i$ 个询问，具体如下：

给定一个空纸堆。

你需要依次处理第 $l_i \sim r_i$ 张纸，当轮到处理某一张纸时，你可以有以下三个选择：

$1$、将其放到堆顶。

$2$、将其放到堆底。

$3$、不将其置于堆中。

在所有待处理纸张均处理完毕后，将纸堆中的所有纸从上到下读取一遍，将读取到的数字按读取顺序组成一个整数。

分析整个处理过程，每张纸有 $3$ 种处理方式，一共有 $r_i-l_i+1$ 张纸，利用排列知识可以得到，一共有 $3^{r_i-l_i+1}$ 种不同的处理方式。

请你计算，所有 $3^{r_i-l_i+1}$ 种不同的处理方式中，最终组成的整数在 $[A,B]$ 范围内的处理方式有多少种，将结果对 $10^9+7$ 取模后输出。

【输入格式】

第一行包含三个整数 $N,A,B$。

第二行包含 $N$ 个整数 $a_1,a_2,...,a_N$。

第三行包含整数 $Q$。

接下来 $Q$ 行，每行包含两个整数 $l_i,r_i$。

【输出格式】

每个询问输出一行结果。

【样例1输入】

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

【样例1输出】

2
18
34

【样例2】

点击下载样例2

【样例1解释】

对于第一个询问，纸张 $1,2$ 共有 $9$ 种不同的处理方式：

纸张 $1$ 不放入纸堆，纸张 $2$ 不放入纸堆，最终得到 $0$。

纸张 $1$ 不放入纸堆，纸张 $2$ 置于堆顶，最终得到 $2$。

纸张 $1$ 不放入纸堆，纸张 $2$ 置于堆底，最终得到 $2$。

纸张 $1$ 置于堆顶，纸张 $2$ 不放入纸堆，最终得到 $1$。

纸张 $1$ 置于堆顶，纸张 $2$ 置于堆顶，最终得到 $21$。

纸张 $1$ 置于堆顶，纸张 $2$ 置于堆底，最终得到 $12$。

纸张 $1$ 置于堆底，纸张 $2$ 不放入纸堆，最终得到 $1$。

纸张 $1$ 置于堆底，纸张 $2$ 置于堆顶，最终得到 $21$。

纸张 $1$ 置于堆底，纸张 $2$ 置于堆底，最终得到 $12$。

只有 $2$ 种处理方式最终得到的整数 $21$ 位于 $[13,327]$ 范围内，因此答案是 $2$。

【数据规模与约定】

测试点 $1-1: B<100$

测试点 $3-4: A=B$

全部数据，满足：$1 \le N \le 300,1 \le A \le B \lt 10^{18},1 \le a_i \le 9,1 \le Q \le 5 \times 10^4,1 \le l_i \le r_i \le N$。