再编号

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

题目描述

n 个人，每个人有一个编号 a_i 。

定义对 a 的再编号为 a' ，满足 $a'_{i}=( \displaystyle \sum_{j=1}^{n} a_{j} )-a_{i}$ 。

现在有 m 次询问，每次给定 x,t ，表示询问经过 t 次再编号后第 x 个人的编号。

由于答案可能很大，所以对 10⁹+7 取模。

输入描述:

第一行 2 个数 n,m ，表示人数和询问次数；

接下来一行 n 个数，表示 a_i ；

接下来 m 行，每行 2 个数 x,t ，描述一次询问。

输出描述:

m 行，第 i 行 1 个数表示第 i 次询问的答案对 10⁹+7 取模的结果。

示例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 ≤ a_i ≤ 10⁹