如果p是一个质数，而a是与p互质的任一整数，则有a^（p-1）≡1（mod p）。
费马小定理
本题6421是一个质数，根据费马小定理：如果一个数 a 不是 6421 的倍数，那么 a 的 6420 次方除以 6421 的余数是 1。
这就意味着：a 的次方，只看指数除以 6420 的余数就够了。
也就是说，要计算x^x除以6421的余数，只需要看底数x除以6421的余数，指数x除以6420的余数。
#include<bits/stdc++.h>
using namespace std;
long long ans,a[6500],b[6500];
long long qpow(long long a,long long b){
long long ans=1;
while(b){
if(b&1) ans=ans*a%6421;
b/=2;
a=a*a%6421;
}
return ans;
}
int main(){
// 计算 x^(x-1) mod 6421 的数量
for(int i=1;i<=20240601;i++) a[qpow(i%6421,i%6420)]++;
for(int i=0;i<6421;i++){
int j=(6421-i)%6421;
if(i<j) ans+=a[i]*a[j];
else if(i==j) ans+=a[i]*(a[i]-1)/2;
}
printf("%lld",ans);
return 0;
}