1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 typedef unsigned long long ll; 5 using namespace std; 6 const int MAXN = 1023; 7 ll f[MAXN][MAXN*10]; 8 int circle[MAXN]; 9 10 void init(){11     for(int k = 2; k<= 1000; k++){12         f[k][0] = 0, f[k][1] = 1;13         for(int i = 2; ; i++){14             f[k][i] = (f[k][i-1] + f[k][i-2])%k;15             if(f[k][i] == 1 && f[k][i-1] == 0){16                 circle[k] = i-1;17                 break;18             }19         }20     }21 }22 ll quick_mod(ll a, ll b, ll mod){23     ll ans = 1;24     while(b > 0){25         if(b&1){26             b--;27             ans = ans*a%mod;28         }29         b >>= 1;30         a = a*a%mod;31     }32     return ans;33 }34 void slove(ll a, ll b, int n){35     int res = quick_mod(a%circle[n], b, circle[n]);36     cout << f[n][res] << endl;37 }38 int main() {39     //freopen("data.in.txt", "r", stdin);40    // freopen("data.out.txt", "w", stdout);41     int t, n;42     ll a, b;43     init();44     scanf("%d", &t);45     while(t--) {46         cin >> a >> b >> n;47         if(n == 1 || a == 0) cout<<0 << endl;;48         else slove(a, b, n);49     }50     return 0;51 }