问题 J: Calculate

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×ki+bi.

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 109+7109+7

The first line, input a positive integer $T(1\le T\le 5)$, representing the number of test data.

For each test, first line input a row of two positive integers �,�(1<�,�≤105)n,q(1<n,q≤105), representing the number of points in the map and the number of queries.

The next line inputs $n$ positive integers ��(1≤��≤105)ki(1≤ki≤105) representing the value of $k$ on each vertex

The next line inputs $n$ positive integers ��(1≤��≤105)bi(1≤bi≤105) representing the value of $b$ on each vertex

The next line inputs $n$ positive integers ��(1≤��≤�)pi(1≤pi≤n) represents the vertex reachable from vertex $i$, guaranteeing ��≠�pi=i.

The next $q$ lines,each line has three positive integers ��,��,��(1≤��≤�,1≤��≤109,1≤��≤105)xi,li,yi(1≤xi≤n,1≤li≤109,1≤yi≤105) for a query,��xi is the vertex where Ming started, ��li is the number of steps Ming took, and ��yi is the number in Ming's hand.

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

18
125
77
221 
9