Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.1 kB
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

bool isSorted(const std::vector<int>& vec) {
    for (int i = 0; i < vec.size() - 1; i++) {
        if (vec[i] > vec[i + 1]) {
            return false;
        }
    }
    return true;
}

#define LL long long 
const int MOD = 1000000007;

LL modPow(LL base, LL exponent) {
    if (exponent == 0) {
        return 1;
    }

    LL result = 1;
    base = base % MOD;

    for (int i = 0; i < exponent; ++i) {
        result = (result * base) % MOD;
    }

    return result;
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1, -1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    vector<int> b(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        b[i] = i;
    }

    int ans = 0;
    // perform operations
    while (ans == 0 || !isSorted(b)) {
        ans++;
        vector<int> new_b(n + 1, -1);
        for (int i = 1; i <= n; ++i) {
            new_b[i] = b[a[i]];
        }
        b = new_b;
    }

    cout << modPow(2, ans) << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}