unsigned __int64 MulMod(unsigned __int64 a,unsigned __int64 b,unsigned __int64 m)  // (a*b)%n = (a%n)*(b%n)%n
{
    // return (a % n)*(b % n )% n; will overflow!so...
    unsigned __int64 s = 0, i;
    a %= m; 
    b %= m;
    for (i=b; i>0; a = (a<<1)%m,i>>=1)
        if (i&1) 
            s = (s+a) % m;
        return s;
}

unsigned __int64 PowMod(unsigned __int64 base,unsigned __int64 pow,unsigned __int64 n)//a^b mod n
{
    unsigned __int64  a=base, b=pow, c=1;
    while (b)
    {
        while( !(b & 1) )
        {
            b>>=1;
            a= MulMod(a, a, n);
        }
        b--;
        c=MulMod(a, c, n);
    }
    return c;
}