n 个人，每个人有一个编号 ai 。 定义对 a 的再编号为 a' ，满足 。 现在有 m 次询问，每次给定 x,t ，表示询问经过 t 次再编号后第 x 个人的编号。 由于答案可能很大，所以对 109+7 取模。
输入描述:
第一行 2 个数 n,m ，表示人数和询问次数；接下来一行 n 个数，表示 ai ；接下来 m 行，每行 2 个数 x,t ，描述一次询问。


输出描述:
m 行，第 i 行 1 个数表示第 i 次询问的答案对 109+7 取模的结果。
示例1

输入

4 3
1 2 3 4
1 0
2 2
4 1

输出

1
22
6

说明

初始编号：1  2  3  4

1 次再编号后：9  8  7  6

2 次再编号后：21  22  23  24

备注:
n ≤ 100000 , m ≤ 10000 , t ≤ 100000 , 1 ≤ ai ≤ 109
加载中...