题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$ ，及 $q$ 组询问，每组询问包含两个正整数 $L_i,R_i$，请你对于每组询问，求出在给定区间 $a_{L_i},...,a_{R_i}$ 之间，有多少个子序列的和为 $m$ 的倍数。（子序列允许为空；由于答案可能过大，输出答案对$10^9+7$取模即可）

输入格式

输入第一行，三个正整数 $n,m,q$ 输入第二行，$n$ 个正整数 $a_1,...,a_n$ 接下来 $q$ 行，每行两个正整数，其中第 $i+2$ 行的正整数分别表示第 $i$ 次询问的 $L_i,R_i$

输出格式

输出共 $q$ 行，每行一个整数表示答案。

4 3 3
7 0 8 6
1 2
1 3
2 4

2
4
4

样例解释 1

对于第1个询问，有2个子序列满足要求：{} {0} 对于第2个询问，有4个子序列满足要求：{} {0} {7,8} {7,0,8} 对于第3个询问，有2个子序列满足要求：{} {0} {6} {0,6}

数据范围

• 对于 $30\%$ 的数据，$1\leq n,q \leq 10$ ，$1 \leq m \leq 5$
• 对于 $60\%$ 的数据，$1\leq n,q \leq 10^3$，$1 \leq m \leq 10$
• 对于 $100\%$ 的数据，$1\leq n,q \leq 10^5$，$1 \leq L_i \leq R_i \leq n$， $0 \leq a_i \leq 10^9$，$1 \leq m \leq 20$