1
long long quickpow(long long base, long long exp, long long mod) {
2
    long long result = 1;
3
    base %= mod;
4
    while (exp > 0) {
5
        if (exp & 1) result = result * base % mod;
6
        base = base * base % mod;
7
        exp >>= 1;
8
    }
9
    return result;
10
}

1
int fa[MAXN];
2

3
void init(int n) {
4
    for (int i = 1; i <= n; i++) fa[i] = i;
5
}
6

7
int find(int x) {
8
    return fa[x] == x ? x : fa[x] = find(fa[x]);
9
}
10

11
void unite(int x, int y) {
12
    fa[find(x)] = find(y);
13
}