$x^x$我们可以通过快速幂来求出

问题在于如何求出$a_1+a_2+…+a_k=g(x)$

对于样列 $a_1+a_2+a_3=4$
我们假设有4个小球 O O O O,我们从中间插入两块板子，那么小球会被分成三堆
O | O O | O 那么每堆的数量就是一个解，其板子不同的放法对应不同的解，那么问题就变成了$C^2_3$

所以我们只需要求出从n-1个缝隙中插入k-1个板子的方法数就行了
由于答案没有取模，所以我们需要运用高精度

#include<bits/stdc++.h>
using namespace std;
const int mod=1000;

int qmi(int a,int n)
{
    int res=1;
    while(n)
     {
        if(n&1) res=res*a%mod;
        a=a*a%mod;
        n>>=1;
     }
    return res;
}

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

vector<int> div(vector<int> &A, int b)
{
    vector<int> C;
    int r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    int k,x;
    cin>>k>>x;

    int g=qmi(x%1000,x);

    g--;
    k--;
    vector<int>a,b;
    a.push_back(1);

    for(int i=1;i<=g;i++) a=mul(a,i);
    for(int i=1;i<=k;i++) a=div(a,i);
    for(int i=1;i<=g-k;i++) a=div(a,i);
    for(int i=a.size()-1;i>=0;i--) cout<<a[i];

    return 0;
}