[Solution] Make Them Alike Solution Codechef

You are given a permutation $P$ of length $N$ , an array $A$ of size $N$ , and an integer $M$ .

Initially, $0 \leq A_{i} \leq M$ . Consider an array $A^{'}$ obtained from $A$ by replacing all zeros in $A$ with positive integers less than equal to $M$ .

The array $A^{'}$ will then be transformed as follows, in $N$ steps:

In the $i^{t h}$ step, we set $A_{i'} = A_{P i'}$ .

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 $\leq M$ . Since this number can be huge, print this number modulo $1 0^{9} + 7$ .

Note that a permutation of length $N$ contains of all elements from $1$ to $N$ exactly once.

Input Format Make Them Alike Solution Codechef

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 $P_{1}, P_{2}, \dots, P_{N}$ , the permutation $P$ .
- The third line of each test case consists of $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ , the initial array $A$ .

Output Format Make Them Alike Solution Codechef

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 $\leq M$ .

Constraints Make Them Alike Solution Codechef

$1 \leq T \leq 1 0^{5}$
$1 \leq N \leq 2 \cdot 1 0^{5}$
$1 \leq M \leq 1 0^{9}$
$0 \leq A_{i} \leq M$
The sum of $N$ over all test cases won’t exceed $2 \cdot 1 0^{5}$ .

Sample 1: Make Them Alike Solution Codechef

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: Make Them Alike Solution Codechef

Test case $1$ : The given permutation is $[2, 1, 4, 3]$ . One of the possible beautiful arrays is: $A^{'} = [1, 2, 3, 2]$ . This is obtained by replacing the first $0$ with $1$ and the second $0$ with $3$ in the array $A$ .
For the transformation:

In the first step, $A_{1'}$ is replaced with $A_{P 1'} = A_{2'}$ , that is $2$ . The array becomes $[2, 2, 3, 2]$ .
In the second step, $A_{2'}$ is replaced with $A_{P 2'} = A_{1'}$ , that is $2$ . The array becomes $[2, 2, 3, 2]$ .
In the third step, $A_{3'}$ is replaced with $A_{P 3'} = A_{4'}$ , that is $2$ . The array becomes $[2, 2, 2, 2]$ .
In the fourth step, $A_{4'}$ is replaced with $A_{P 4'} = A_{3'}$ , that is $2$ . The array becomes $[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]$ .

There are $9$ beautiful arrays in total.