一、快速幂：

ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

二、矩阵快速幂：

#include<cstring>
#define ll long long
const int maxn=12;
struct Ma
{
    ll m[maxn][maxn];
};

Ma mul(Ma a,Ma b,int n)
{
    Ma temp;
    memset(&temp,0,sizeof(temp));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
        temp.m[i][j]+=a.m[i][k]*b.m[k][j];

    return temp;
}

Ma mypow(Ma res,int N,int n)
{
    Ma ans;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(i==j) ans.m[i][j]=1;
        else ans.m[i][j]=0;

    while(N)
    {
        if(N&1) ans=mul(ans,res,n);
        res=mul(res,res,n);

        N>>=1;
    }
    return ans;
}