再编号
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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