// Author：A Fei
///solution: 隔板法
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[1000][100][150];

// 快速幂
int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }

    return res;
}

// 高精加
void add(int c[], int a[], int b[])
{
    for(int i = 0, t = 0; i < 150; i ++)
    {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
}

int main()
{
    int n, k;
    scanf("%d%d", &k, &n);

    n = qmi(n % 1000, n, 1000);

    //求C(n - 1, k - 1);
    // C(n, m) = C(n - 1, m - 1) + C(n - 1, m);
    for(int i = 0; i < n; i ++)
        for(int j = 0; j <= i && j < k; j ++)
            if(!j) f[i][j][0] = 1;
            else add(f[i][j], f[i - 1][j - 1], f[i - 1][j]);

    // 重定义一下，方便
    int *g = f[n - 1][k - 1];
    int idx = 149;
    // 从非零位输出
    while(!g[idx]) idx--;
    for(int i = idx; i >= 0; i --) printf("%d", g[i]);

    return 0;
}