Colossal Fibonacci Numbers!

The i‘th Fibonacci number f (i) is recursively defined in the following way:

• f (0) = 0 and f (1) = 1
• f (i+2) = f (i+1) + f (i)  for every i ≥ 0

Your task is to compute some values of this sequence.

Input begins with an integer t ≤ 10,000, the number of test cases.Each test case consists of three integersa,b,n where 0 ≤ a,b < 2⁶⁴(a and b will not both be zero)and 1 ≤ n ≤ 1000.

For each test case, output a single linecontaining the remainder of f (a^b) upon division byn.

Sample input

3
1 1 2
2 3 1000
18446744073709551615 18446744073709551615 1000

Sample output

1
21
250

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<vector>
using namespace std;
typedef unsigned long long ULL;//long long 挂
ULL n,m,MOD;
vector<int>f[1001];
void init()
{
    for(int i=2;i<=1000;i++)
    {
        int mod=i;
        int a=0,b=1,c=(a+b)%mod;
        f[i].push_back(a);
        f[i].push_back(b);
        f[i].push_back(c);
        while(!(b==0&&c==1))
        {
            a=b;
            b=c;
            c=(a%mod+b%mod)%mod;
            f[i].push_back(c);
        }
        f[i].pop_back();
        f[i].pop_back();
    }
}
ULL quick_mod(ULL a,ULL b,ULL m)//快速幂缩小区间
{
     ULL ans = 1;
     while(b)
     {
        if(b&1)
        {
            ans=((ans%m)*(a%m))%m;
            b--;
        }
        b/=2;
        a=((a%m)*(a%m))%m;
     }
     return ans;
}
int main()
{
    int t;
    cin>>t;
    init();//打表
    while(t--)
    {
        cin>>n>>m>>MOD;
        if(MOD==1)
        {
            cout<<0<<endl;
            continue;
        }
        ULL mm=f[MOD].size();
        ULL ans=quick_mod(n,m,mm);
        cout<<f[MOD][ans]<<endl;
    }
    return 0;
}