题目内容

在一个由 $n$ 个房间组成的迷宫中，每个房间都有一个传送装置，从房间 $i$ 会立即被传送到房间 $a_i$。你选择了一个起点房间，每次进入房间时都会累积积分：如果是第 $t$ 次进入房间 $x$（无论全局次数），则此次访问获得 $t imes x$ 分。请注意，初始站上起点房间也算作第一次进入。

现有 $q$ 个独立的询问，每个询问给出起点房间编号 $p$ 和总进入次数 $k$（包括第一次进入起点）。你需要对每个询问计算经过 $k$ 次进入后获得的总积分，并将结果对 $10^9+7$ 取模。

约束条件：房间总数 $n$ 与询问个数 $q$ 不超过 $2 imes 10^5$；数组 $a_i$ 中的每个目标均在 $1$ 到 $n$ 之间；每个询问的总进入次数 $k$ 不超过 $10^9$。

输入描述

第一行包含两个整数 $n$ 和 $q$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个房间的传送目标。 接下来 $q$ 行，每行包含两个整数 $p, k$，表示一次询问的起点房间和总进入次数。

输出描述

对于每个询问，输出一行一个整数，表示该询问的总积分对 $10^9+7$ 取模后的结果。

样例1

输入

3 3
2 3 1
1 1
1 5
2 3

输出

1
12
6

说明

迷宫有 3 个房间，传送规则为 $1 \rightarrow 2$, $2 \rightarrow 3$, $3 \rightarrow 1$，形成一个长度为 3 的循环。

• 询问 1：起点 $p=1$，总进入次数 $k=1$。仅进入房间 1 一次，积分 $1 imes 1 = 1$。
• 询问 2：起点 $p=1$，$k=5$。路径为 $1$（第 1 次）$\rightarrow 2$（第 1 次）$\rightarrow 3$（第 1 次）$\rightarrow 1$（第 2 次）$\rightarrow 2$（第 2 次）。积分分别为 $1 imes1=1$, $2 imes1=2$, $3 imes1=3$, $1 imes2=2$, $2 imes2=4$，总和 $1+2+3+2+4=12$。
• 询问 3：起点 $p=2$，$k=3$。路径为 $2$（第 1 次）$\rightarrow 3$（第 1 次）$\rightarrow 1$（第 1 次）。积分 $2 imes1 + 3 imes1 + 1 imes1 = 6$。

样例2

输入

2 2
2 2
1 4
2 2

输出

13
6

说明

迷宫有 2 个房间，传送规则为 $1 \rightarrow 2$, $2 \rightarrow 2$。房间 2 是一个自环，一旦进入就会一直停留在房间 2。

• 询问 1：起点 $p=1$，$k=4$。路径为 $1$（第 1 次）$\rightarrow 2$（第 1 次）$\rightarrow 2$（第 2 次）$\rightarrow 2$（第 3 次）。积分 = $1 imes1 + 2 imes1 + 2 imes2 + 2 imes3 = 1 + 2 + 4 + 6 = 13$。
• 询问 2：起点 $p=2$，$k=2$。路径为 $2$（第 1 次）$\rightarrow 2$（第 2 次）。积分 = $2 imes1 + 2 imes2 = 6$。

样例3

输入

1 2
1
1 1
1 1000000000

输出

1
21

说明

迷宫只有 1 个房间，传送规则为 $1 \rightarrow 1$。每次进入都是房间 1，第 $t$ 次进入获得 $t imes 1 = t$ 分。总积分即为 $1 + 2 + \dots + k = \frac{k(k+1)}{2}$。

• 询问 1：$p=1, k=1$，积分 $= 1$。
• 询问 2：$p=1, k=10^9$。需要计算 $\frac{10^9 imes (10^9+1)}{2} \bmod (10^9+7)$。令 $M=10^9+7$，有 $10^9 \equiv -7 \pmod M$，因此分子 $\equiv (-7) imes(-6) = 42$，除以 2 得 $21 \bmod M$。故输出 21。