Make Them Alike.cpp

#ifdef DEBUG
#include "debug.h"
#endif // DEBUG
#ifndef DEBUG
template <typename T>
void debug(T &x){}
template <typename T>
void debug(T &x, int i, int j){}
#endif // DEBUG

#include <bits/stdc++.h>

using namespace std;

const long long int mod = 1e9 + 7;

long long int Pow(long long int x, long long int y){
    if(y == 0) return 1;
    long long int res = Pow(x, y / 2);
    res = res * res % mod;
    if(y & 1) res = res * x % mod;
    return res;
}

int main(){
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--){
        int N, M, zeroNum = 0;
        cin >> N >> M;
        vector <int> P(N + 1), A(N + 1);
        for(int i = 1; i <= N; i++) cin >> P[i];
        for(int i = 1; i <= N; i++) cin >> A[i];
        for(int i = 1; i <= N; i++){
            if(A[i] == 0) zeroNum++, A[i] = M + i;
        }

        for(int i = 1; i <= N; i++){
            A[i] = A[P[i]];
        }

        debug(A);

        set <int> s;
        for(int i = 1; i <= N; i++){
            if(A[i] <= M) s.insert(A[i]);
        }

        if((int)s.size() >= 2) cout << "0\n";
        else{
            s.clear();
            bool allZero = true;

            for(int i = 1; i <= N; i++){
                if(A[i] > M) s.insert(A[i]);
                if(A[i] <= M) allZero = false;
            }
            zeroNum -= (int)s.size();

            long long int ans = Pow(M, zeroNum);
            if(allZero) ans = ans * M % mod;
            cout << ans << "\n";
        }
    }
}