题意：
思路：
模板代码：
// -----------------
//#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <algorithm>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
#define endl '\n'
#define int long long
using namespace std;
int a,m;
string s;
int qmi(int a, int k, int p)
{
int res = 1 % p;
while (k)
{
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
int phi(int x) // 暴力筛欧拉数
{
int res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
void solve()
{
cin >> a >> m;
cin >> s;
int mod = phi(m);
int ans = 0,ff = 0;
for(int i = 0; i < s.size(); i ++)
{
ans = ans * 10 + (s[i] - '0');
if(ans >= mod ) ff = 1,ans %= mod;
}
if(ff) ans += mod; // ans 大于过 mod
cout << qmi(a, ans, m) << endl;
}
signed main()
{
IOS
int T = 1;
//cin >> T;
while(T --) { solve(); }
return 0;
}