#define ll long long int
#define mod %1000000007
ll fastexpo(ll a, ll n)
{
    ll ret=1;
    ll b=a;
    while(n)
    {
        if(n&1)ret=(ret*b)mod;  //if(n==odd)	
        b=(b*b)mod;		
        n>>=1; 			// n/=2
    }
    return (ll)ret;
}