求 $N^M \bmod 129403207$。

$0 \le N,M \le 10^{{10}^5}$。

用扩展欧拉定理过不去样例。

#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int N=1e5+10,MOD=129403207,PHI=129403206; char s[N];
signed main() {
  scanf("%s",s+1);
  int x=0; bool flag=false; char ch=getchar();
  while(ch<'0'||ch>'9') ch=getchar();
  while(ch>='0'&&ch<='9') {
    x=x*10+ch-'0';
    if(x>=PHI) x%=PHI,flag=true;
	ch=getchar();
  }
  if(x>=PHI) flag=true,x%=PHI;
  if(flag) x+=PHI;
  int l=strlen(s+1),r=0;
  for(int i=1;i<=l;i++) r=(r*10+s[i]-'0')%MOD;
  int ans=1;
  while(x) {
  	if(x&1) ans=ans*r%MOD;
  	r=r*r%MOD,x>>=1;
  }
  printf("%lld",ans);
  return 0;
}

1in:

7382974343
3432476397

1out:27853659

2in:

129402306
129402306

2out:1