题目描述

一个景区中有 $n$ 个景点，编号为 $1\sim n$。景点 $i$ 的美观度为 $a_i$。

景区的游览顺序固定：如果当前位于景点 $i$，下一个游览的景点必须是 $b_i$。一个景点的后继可以是它自己，游览过程中也可以多次经过同一景点。

小 A 将进行 $q$ 次游玩。每次给出 $p,c$，表示从景点 $p$ 开始，连续游览 $c$ 个景点。起点 $p$ 是本次游览的第 $1$ 个景点。

如果本次游览的第 $j$ 个景点是 $x$，小 A 获得的快乐度为 $(a_x+j)^2$。

对于每次游玩，求快乐度总和对 $10^9+7$ 取模后的结果。

输入格式

在文件 travel.in 中读入。

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

第三行 $n$ 个整数 $b_1,b_2,\ldots,b_n$。

第四行一个整数 $q$。

接下来 $q$ 行，每行两个整数 $p,c$，描述一次游玩。

输出格式

在文件 travel.out 中输出。

输出 $q$ 行，每行一个整数，表示对应游玩的答案。

样例

样例输入 #1

5
3 2 1 4 5
3 3 1 2 4
2
3 5
1 6

样例输出 #1

130
199

样例 1 解释

第一次游览依次经过景点 $3,1,3,1,3$，快乐度为

数据范围

本题共 $20$ 个测试点，每点 $5$ 分。

对于所有测试数据：

其他限制

• 时间限制：$1\text{ s}$；
• 空间限制：$256\text{ MiB}$。