``````#include<stdio.h>
#define ll long long
ll FastPower(ll a,ll b,int mod);
int main()
{

ll a, b , mod;

scanf("%lld %lld %lld",&a,&b,&mod);
long long res = FastPower(a,b,mod);				//res为a ^ b % mod  的结果
printf("%lld\n",res);

return 0;
}
ll FastPower(ll a,ll b,int mod)
{
ll result=1;
while(b)
{
if(b&1)
result = (result * a) % mod;
b>>=1;
a = (a * a) % mod;
}
return result;

}
``````

``````#include<algorithm>
#include<stdio.h>
#include<string.h>
#define ll long long
using namespace std;
const ll Mod =1000000009;
struct Mat
{
int n, m;

ll data[4][4];
};

Mat ans;

Mat MatMul(Mat a, Mat b);

Mat MatMod(Mat a, ll mod);		//矩阵取模

Mat MatFastPoswer(Mat a, ll k, ll mod);

int main()
{

int n,m;
scanf("%d %d",&n, &m);		//输入矩阵的行数和列数

Mat data;
data.n = n;
data.m = m;
for(int i = 1; i <= n; i++)			//输入矩阵。
{
for(int j = 1; j <= m; j++)
scanf("%lld",&data.data[i][j]);
}
ll k;						//幂次
ll mod;
scanf("%lld %lld",&k, &mod) ;

Mat result = MatFastPoswer(data, k ,mod);

for(int i = 1; i <= result.n; i++)			//输出矩阵
{
for(int j = 1; j <= result.m; j++)
printf("%lld ",result.data[i][j]) ;
printf("\n");
}

return 0;
}

Mat MatFastPoswer(Mat a, ll k, ll mod)
{
int maxn = max(a.n,a.m);

ans.n =  ans.m = maxn;

memset(ans.data, 0 , sizeof(ans.data));
for(int i =1; i <= ans.n; i++)
ans.data[i][i] = 1;

Mat res;
res = a;
while(k)
{
if(k & 1)
ans = MatMod(MatMul(ans,res), mod);

res = MatMod(MatMul(res, res), mod);

k = k >> 1;
}

return ans;

}

Mat MatMul(Mat a, Mat b)
{
Mat temp ;

temp.n = a.n, temp.m = b.m;

for(int i = 1; i <= temp.n; i++)
{
for(int j =1; j <= temp.m; j++)
{
temp.data[i][j] = 0;

for(int k = 1; k <= temp.m; k++)
{
temp.data[i][j] += (a.data[i][k] * b.data[k][j]);
}
}
}
return temp;
}
Mat MatMod(Mat a, ll mod)
{
Mat temp = a;

for(int i = 1; i <= temp.n; i++)
{
for(int j = 1; j <= temp.m; j++)
{
temp.data[i][j] %= mod;
}
}

return temp;
}``````