#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define pii pair<int, int>

using namespace std;

const int N = 1e6 + ;

const int M = 1e6 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 +;

LL fastPow(LL a, LL b) {

    LL ans = ;

    while(b) {

        if(b & ) ans = ans * a % mod;

        a = a * a % mod; b >>= ;

    }

    return ans;

}

LL a, n;

char s[N];

int main(){

    scanf("%lld%s", &a, s);

    int len = strlen(s);

    for(int i = ; i < len; i++) {

        n = n *  % (mod - );

        n += s[i] - '';

        if(n >= mod - ) n -= mod - ;

    }

    a = a * fastPow(10000ll, mod - ) % mod;

    a =  -  * a;

    a = ((a % mod) + mod) % mod;

    a = fastPow(a, n);

    a =  - a;

    if(a < ) a += mod;

    a = a * fastPow(, mod - ) % mod;

    printf("%lld\n", a);

    return ;

}

/*

*/