P4760. 跳转指令的开销

场次：2026年4月11日-开发岗 · 来源：CodeFun2000 P4760

题目描述

有一个特殊的程序，包含 n 条指令，编号为 1 到 n。程序在执行时会按照一个固定的跳转规则移动：执行完指令 i 后，一定会跳转到指令 $next_i$，其中 $1 \le next_i \le n$。

每次执行指令 i 时，如果这是该指令在程序运行过程中第 t 次被执行，那么这一次就会产生 $t \times i$ 的计算开销。注意这里的 t 是对每一条指令独立计数的，即只统计该指令自身被执行的次数。

现在有 q 次询问。每次询问给定一个起始指令 p 和一个整数 k，表示程序从指令 p 开始执行，并且一共执行 k 条指令（包含起始的那一次）。对于每个询问，你需要输出程序在这 k 条指令的执行过程中产生的总开销，结果对 $10^9+7$ 取模。

数据范围：指令数量 n 与询问数量 q 均不超过 2×10^5；跳转目标 $next_i$ 均为 1 到 n 之间的整数；对于每个询问，起始指令 p 满足 $1 \le p \le n$，执行次数 k 满足 $1 \le k \le 10^9$。

输入格式

第一行输入两个整数 n 和 q，分别表示指令条数和询问个数。 第二行输入 n 个整数 $next_1, next_2, \dots, next_n$，其中 $next_i$ 表示执行指令 i 后跳转到的指令编号。 此后 q 行，每行输入两个整数 p 和 k，表示从指令 p 开始执行、一共执行 k 次（含起始那次）的一组询问。

输出格式

对于每个询问，输出一行一个整数，表示这 k 次执行产生的总开销对 $10^9+7$ 取模后的结果。

示例

示例 1

输入：

1 2
1
1 1
1 5

输出：

1
15

说明：

只有一条指令 $1$，每次执行产生的开销为 $t \times 1$。 对于查询 1 1，$k=1$，总开销为第 $1$ 次执行 $1$ 的开销 $1$。 对于查询 1 5，$k=5$，连续执行第 $1$ 至第 $5$ 次，总开销为 $1+2+3+4+5=15$。

示例 2

输入：

2 3
2 1
1 1
1 4
2 3

输出：

1
9
7

说明：

指令 $1$ 和 $2$ 构成长度为 $2$ 的环，跳转规则为 $1 \to 2$，$2 \to 1$。

• 查询 1 1：仅执行指令 $1$ 一次，开销 $1 \times 1 = 1$。
• 查询 1 4：执行序列 $1,2,1,2$。指令 $1$ 执行了第 $1,2$ 次，产生开销 $1 \times 1 + 2 \times 1 = 3$；指令 $2$ 执行了第 $1,2$ 次，产生开销 $1 \times 2 + 2 \times 2 = 6$；总和为 $9$。
• 查询 2 3：执行序列 $2,1,2$。指令 $2$ 执行了第 $1,2$ 次，开销 $1 \times 2 + 2 \times 2 = 6$；指令 $1$ 执行了第 $1$ 次，开销 $1 \times 1 = 1$；总和为 $7$。

示例 3

输入：

5 4
2 3 4 2 4
1 2
1 8
5 4
5 10

输出：

3
34
14
59

说明：

图结构：环为 $2 \to 3 \to 4 \to 2$，长度 $L=3$。指令 $1$ 指向 $2$（距环 $1$ 步），指令 $5$ 指向 $4$（距环 $1$ 步）。

• 查询 1 2：执行 $1,2$，开销 $1 + 1 \times 2 = 3$。
• 查询 1 8：先执行树边部分 $1$（开销 $1$），再在环上执行 $7$ 次（完整两轮余 $1$ 次）。序列 $1,2,3,4,2,3,4,2$，各指令计数与开销：$1$ 一次 $1$；$2$ 三次 $2+4+6=12$；$3$ 两次 $3+6=9$；$4$ 两次 $4+8=12$；合计 $34$。
• 查询 5 4：执行 $5,4,2,3$，各执行一次，开销 $5+4+2+3=14$。
• 查询 5 10：先执行一次 $5$（开销 $5$），环上执行 $9$ 次（完整三轮）。$4,2,3$ 各执行三次，开销分别为 $4+8+12=24$，$2+4+6=12$，$3+6+9=18$，总和 $5+24+12+18=59$。