Problem
You are given a permutation �P of length �N, an array �A of size �N, and an integer �M.
Initially, 0≤��≤�0≤Ai≤M. Consider an array �′A′ obtained from �A by replacing all zeros in �A with positive integers less than or equal to �M.
The array �′A′ will then be transformed as follows, in �N steps:
- In the ��ℎith step, we set ��′=���′Ai′=APi′.
The initial array �′A′ is said to be beautiful, if, after the transformation of �N steps, all elements of array �′A′ are equal.
Find the number of such beautiful arrays �′A′ which can be formed by changing the zeros in array �A to any value ≤�≤M. Since this number can be huge, print this number modulo 109+7109+7.
Note that a permutation of length �N contains of all elements from 11 to �N exactly once.
Input Format
- The first line of input will contain a single integer �T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers �N and �M, the size of the array and the maximum value it can have.
- The second line of each test case consists of �N space-separated integers �1,�2,…,��P1,P2,…,PN, the permutation �P.
- The third line of each test case consists of �N space-separated integers �1,�2,…,��A1,A2,…,AN, the initial array �A.
Output Format
For each test case, output on a new line, the number of such beautiful arrays �′A′ which can be formed by changing the zeros in array �A to any value ≤�≤M.
Constraints
- 1≤�≤1051≤T≤105
- 1≤�≤2⋅1051≤N≤2⋅105
- 1≤�≤1091≤M≤109
- 0≤��≤�0≤Ai≤M
- The sum of �N over all test cases won’t exceed 2⋅1052⋅105.
Sample 1:
Input
Output
3 4 3 2 1 4 3 0 2 0 2 3 2 3 1 2 0 0 0 8 54 8 1 2 4 3 6 7 5 0 0 0 0 0 0 0 0
9 8 459165024
Explanation:
Test case 11: The given permutation is [2,1,4,3][2,1,4,3]. One of the possible beautiful arrays is: �′=[1,2,3,2]A′=[1,2,3,2]. This is obtained by replacing the first 00 with 11 and the second 00 with 33 in the array �A.
For the transformation:
- In the first step, �1′A1′ is replaced with ��1′=�2′AP1′=A2′, that is 22. The array becomes [2,2,3,2][2,2,3,2].
- In the second step, �2′A2′ is replaced with ��2′=�1′AP2′=A1′, that is 22. The array becomes [2,2,3,2][2,2,3,2].
- In the third step, �3′A3′ is replaced with ��3′=�4′AP3′=A4′, that is 22. The array becomes [2,2,2,2][2,2,2,2].
- In the fourth step, �4′A4′ is replaced with ��4′=�3′AP4′=A3′, that is 22. The array becomes [2,2,2,2][2,2,2,2].
Thus, after the transformation, all elements of the array are equal. The other beautiful arrays for this test case are: [1,2,1,2],[1,2,2,2],[2,2,1,2],[2,2,2,2],[2,2,3,3],[3,2,1,2],[3,2,2,2],[3,2,3,2][1,2,1,2],[1,2,2,2],[2,2,1,2],[2,2,2,2],[2,2,3,3],[3,2,1,2],[3,2,2,2],[3,2,3,2].
There are 99 beautiful arrays in total.
