题意：让你求斐波拉契数列的第a的b次方项模n的结果。
分析：由于是每一项都对n取模，所以不同的n值都会对应一个周期，只要循环一下。当前项等于f1，前一项等于f0时就可以跳出循环了。a的b次方，可以用幂取模的知识，快速分治求出。注意第二个样例a要先模一下周期，不然会有溢出。刚开是long long 也会溢出，所以要用unsigned long long。

代码如下:

//
//Created by BLUEBUFF 2016/1/11
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b) memset(a, b, sizeof(a))
#define MP(x, y) make_pair(x,y)
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 1024;
const int maxm = 1e5+5;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
const int rev = (mod + 1) >> 1; // FWT
//const double PI = acos(-1);
//head

int f[maxn][maxn*6], g[maxn];
LL powmod(uLL a, uLL n, uLL m){
    LL res = 1;
    while(n){
        if(n & 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}

void init(){
    for(int i = 2; i < maxn; i++){
        f[i][0] = 0; f[i][1] = 1;
        for(int j = 2; ;j++){
            f[i][j] = (f[i][j - 1] + f[i][j - 2]) % i;
            if(f[i][j - 1] == 0 && f[i][j] == 1){
                g[i] = j - 1;
                break;
            }
        }
    }
}

int main()
{
    init();
    int T;
    cin >> T;
    uLL a, b, n;
    while(T--){
        cin >> a >> b >> n;
        if(a == 0 || n == 1){
            cout << 0 << endl;
        }
        else{
            int pos = powmod(a % g[n], b, g[n]);
            cout << f[n][pos] << endl;
        }
    }
    return 0;
}