没过样例

#include<iostream>
#include<cmath>
#include<string>
#include<string.h>
#include<algorithm>
#define int long long

using namespace std;

const int N=1e5+5;

int n,m,x;
string s;
int sum1,sum2;

int ksm(int b,int e)
{
	int a=1;
	for (;e;e>>=1,b=1ll*b*b%m)
		if(e&1)
			a=1ll*a*b%m;
	return a;
}

int work(int n)
{
	int ans=n;
	for(int i=2;i<=sqrt(n);i++)
		if(n%i==0)
		{
			ans=ans/i*(i-1);
			while(n%i==0)
				n=n/i;
		}
	if(n>1)
		ans=ans/n*(n-1);
	return ans;
}

int delow(int mod)
{
	int b=0,f=0;
	for(int i=0;i<s.size();i++)
	{
		b=b*10+(s[i]-'0');
		if(b>=mod)
		{
			f=1;
			b=b%mod;
		}
	}
	if(f)
		b+=m;
	return b;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s;
	sum1=work(n);
	sum2=delow(m);
	x=ksm(sum1,sum2);
//	cout<<sum1<<" "<<sum2<<endl;
	cout<<x%m<<endl;
	return 0;
}