fast exponential

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long

set<ll> st;

const ll mod=1e9+7;

ll  powMod ( ll a, ll b ){
    ll ans =1 ;
    for (ll i =1;i<=b;i++){
        ans*=a;
        ans%=mod;
    }
    return ans ;
}

ll solve (ll x , ll n ){
    if ( n==0 ) return 1 ;
    ll last_digit= n%10;
    return  powMod(solve(x,n/10),10) % mod * powMod(x,last_digit) % mod;
}

int main(){
    ll x, n;
    cin >> x >> n;
    ll res= solve ( x,n );
    cout << res;

    return 0;
}