T221264 进制区间
题目背景
前缀计算
题目描述
给定长度为$n$的整数数列$a_i$以及基数$b$。
然后进行$t$次询问，每次给定区间的左右边界$l$、$r$，求将区间内的数看作$b$进制时的数值，其中高位在左。
输出对$10^9 + 7$取模后的结果。
输入格式
第一行包含两个正整数$n$、$t$、$b$。
第二行包含$n$个整数$a_i$。
接下来$t$行，每行包含两个正整数$l$、$r$。
输出格式
对于每个询问输出一行，包含一个整数。
说明/提示
对于30%的数据，$1 ≤ n、t、b ≤ 10$。
对于100%的数据，$1 ≤ n、t、b ≤ 10^5$，$0 ≤ a_i < b$，$1 ≤ l ≤ r ≤ n$。