解题思路

这是一个典型的函数图问题。

对于每个城市 $i$，下一次一定去 $a_i$，因此整张图中每个点出度都为 $1$，图的结构一定是：

• 若干棵树指向某个环
• 若干个独立的环

题目内容

小美同学正在周游世界，她来到了天才之国，这里一共有 $n$ 个城市，编号为 $1,2,…,n$。

她早早做好了规划：当她来到城市 $i$ 时，下一次会去到城市 $a_i$​。

同时，她会获得价值：如果这是她第 $t$ 次来到城市 $i$ ，那么这一次会获得 $t×i$ 的价值。

小美同学提出了 $q$ 个问题。每个问题给出两个整数 $p,k$，表示她从城市 $p$ 出发，并且一共 “来到城市” $k$ 次（包含一开始就在 $p$ 的那次）。请你计算她获得的总价值。

特别注意：第 $1$ 次来到的城市就是起点 $p$ 。

输入描述

第一行输入两个整数 $n,q(1≤n,q≤2×10^5)$，分别表示城市数量与询问数量。

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(1≤a_i≤n)$，其中 $a_i$ 表示从城市 $i$ 下一次会到达的城市编号。

此后 $q$ 行，每行输入两个整数 $p,k(1≤p≤n; 1≤k≤10^9)$，含义见题目描述。

输出描述

对于每个询问，新起一行输出一个整数，表示总价值对109+7取模后的结果。

样例1

输入

3 3
2 3 3
1 1
1 4
3 3

输出

1
12
18

说明

• 对于询问 $p=1,k=1$：只来到城市 $1$ 这一次，获得 $1×1=1$。

• 对于询问 $p=1,k=4$：来到城市的顺序为 $1,2,3,3$。

• 其中城市 $1$ 来了 $1$ 次，贡献为 $1$ ；

• 城市 $2$ 来了 $1$ 次，贡献为 $2$；

• 城市 $3$ 来了 $2$ 次，贡献为 $3×1+3×2=9$。

• 总价值为 $1+2+9=12$。

样例2

输入

4 2
2 1 4 3
1 5
3 2

输出

12
7