[Solution] Make Them Alike Solution Codechef

[Solution] Make Them Alike Solution Codechef

You are given a permutation  of length , an array  of size , and an integer .

Initially, 0≤��≤�. Consider an array �′ obtained from  by replacing all zeros in  with positive integers less than equal to .

The array �′ will then be transformed as follows, in  steps:

  • In the ��ℎ step, we set ��′=���′.

The initial array �′ is said to be beautiful, if, after the transformation of  steps, all elements of array �′ are equal.

Find the number of such beautiful arrays �′ which can be formed by changing the zeros in array  to any value ≤�. Since this number can be huge, print this number modulo 109+7.

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

Input Format Make Them Alike Solution Codechef

  • The first line of input will contain a single integer , 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  and , the size of the array and the maximum value it can have.
    • The second line of each test case consists of  space-separated integers �1,�2,…,��, the permutation .
    • The third line of each test case consists of  space-separated integers �1,�2,…,��, the initial array .

Output Format Make Them Alike Solution Codechef

For each test case, output on a new line, the number of such beautiful arrays �′ which can be formed by changing the zeros in array  to any value ≤�.

Constraints Make Them Alike Solution Codechef

  • 1≤�≤105
  • 1≤�≤2⋅105
  • 1≤�≤109
  • 0≤��≤�
  • The sum of  over all test cases won’t exceed 2⋅105.

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: �′=[1,2,3,2]. This is obtained by replacing the first 0 with 1 and the second 0 with 3 in the array .
For the transformation:

  • In the first step, �1′ is replaced with ��1′=�2′, that is 2. The array becomes [2,2,3,2].
  • In the second step, �2′ is replaced with ��2′=�1′, that is 2. The array becomes [2,2,3,2].
  • In the third step, �3′ is replaced with ��3′=�4′, that is 2. The array becomes [2,2,2,2].
  • In the fourth step, �4′ is replaced with ��4′=�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.

Leave a Comment