Calculate

Problem Description

Ming is on a map. There are $n$ vertexes in the map. For each vertex, there is only one one-way edge that can reach another vertex on the map. Ming has a number $y$ in his hand, and when he reaches a certain vertex $i$, the number in his hand will change to $y\times k_i+b_i$. There are several inquiries, each query Ming will start from a vertex $x$ and walk $l$ steps. At each step Ming starts from the current vertex and proceeds along the outgoing arc of that vertex to the next vertex. The initial number in his hand is $y$, and he wants to know what the number in his hand will become in the end.The answer is modulo $10^9+7$

Input

The first line, input a positive integer $T(1\leq T\leq 5)$, representing the number of test data. For each test, first line input a row of two positive integers $n,q(1< n,q\leq 10^5)$, representing the number of points in the map and the number of queries. The next line inputs $n$ positive integers $k_i(1\leq k_i\leq 10^5)$ representing the value of $k$ on each vertex The next line inputs $n$ positive integers $b_i(1\leq b_i\leq 10^5)$ representing the value of $b$ on each vertex The next line inputs $n$ positive integers $p_i(1\leq p_i\leq n)$ represents the vertex reachable from vertex $i$, guaranteeing $p_i\neq i$. The next $q$ lines,each line has three positive integers $x_i,l_i,y_i(1\leq x_i\leq n,1\leq l_i\leq 10^9,1\leq y_i\leq 10^5)$ for a query,$x_i$ is the vertex where Ming started, $l_i$ is the number of steps Ming took, and $y_i$ is the number in Ming's hand.

Output

For each query, output a line with an integer representing the answer.The answer could be so large that you have to take mod $10^9+7$.

Sample Input

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

Sample Output

18
125
77
221
9

Source

2023“钉耙编程”中国大学生算法设计超级联赛（6）