(a^b)%c

long long power(long long x,int y)
{
    if (!y)
    return 1;
    long long ret=power(x,y/2);
    ret=(ret*ret)%mod;
    if (y%2)
    ret=(ret*x)%mod;
    return ret;
}