rt. 试了好多种写法了，不是RE就WA

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
const int M=1000;
struct bigint{
	int num[151];
	int len;
	bigint(){
		memset(num,0,sizeof num);
		len=0;
	}
	void print(){
		for(int i=len;i>=0;i--)cout<<num[i];
	}
	bigint operator+(bigint A){
		bigint ret;
		ret.len=max(A.len,len);
		for(int i=0;i<=ret.len;i++){
			ret.num[i]=num[i]+A.num[i];
			if(ret.num[i]>=10){
				ret.num[i+1]=ret.num[i]/10;
				ret.num[i]%=10;
			}
		}
		if(ret.num[ret.len])ret.len++;
		while(ret.len and !ret.num[ret.len])ret.len--;
		return ret;
	}
};

int qpow(int x,int k){
	int t=x,ans=1;
	while(k){
		if(k&1)ans=(ans*t)%M;
		k>>=1;
		t=(t*t)%M;
	}
	return ans;
}

int k,x;
bigint c[101][1001];
int main(){
	cin>>k>>x;
	x%=1000;
	int lans=qpow(x,x);
	c[1][0].num[0]=1;
	for(int i=1;i<=k;i++){
		for(int j=i;j<=lans;j++){
			c[i][j]=c[i][j-1]+c[i-1][j-1];
		}
	}
	c[k][lans].print();
	return 0;
}