#define ll long long 

//a^b % mod
ll power(ll a, ll b, ll mod){
    int ans = 1;
    while(b){
        if(b&1)
            ans = (ans * a) % mod;
        b /= 2;
        a = a * a % mod; 
    }
    return ans;
}

int solve(string str1, string str2) {
    ll mod = 1e9+7;
    long long  a = 0 , b = 0;
    
    //reduce b using Euler's theorem ---> a^(m-1) = 1 mod m
    for(ll i=0;i<str2.length();++i){
        b = (b * 10 + (str2[i]-'0'))%(mod-1);
    }
    
    //reduce a using mod 
    for(ll i=0;i<str1.length();++i){
        a = (a * 10 + (str1[i]-'0'))%mod;
    } 

    return power(a,b,mod);
}