1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <cmath>
#include <random>
long long modular_multi(long long x, long long y, long long mo)
{
    long long t;
    x %= mo;
    for (t = 0; y; x = (x << 1) % mo, y >>= 1)
        if (y & 1)
            t = (t + x) % mo;
    return t;
}
long long modular_exp(long long num, long long t, long long mo)
{
    long long ret = 1, temp = num%mo;
    for (; t; t >>= 1, temp = modular_multi(temp , temp, mo))
        if (t & 1)
            ret = modular_multi(ret, temp, mo);
    return ret;
}
int isValid(long long num){
    if (num == 2) return 1;
    if (num % 2 == 0){
        return -1;
    }
    else{
        long long s = 0, r = num - 1, j = 0, t = 8;
        while (r % 2 == 0){
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX