A bit of help with problem ZD

I did not anticipate it at first, but it turns out that problem ZD has a nasty overflow problem. If you try to use the powmod() function from the provided number.cpp, it will fail because the line "r *= r;" will try to square a number that is slightly larger than 2³². There is a rather ugly fix to this. Try using this powmod() function instead of the one from the collection of number theoretic algorithms.

typedef unsigned long long ull;

/**
 * Multiplies two numbers and returns the product modulo n
 * ull is unsigned long long
 **/
ull multmod( ull a, ull b, ull n )
{
    ull a0 = a & 0xFFFFFFFFLL;
    ull a1 = a >> 32;
    ull b0 = b & 0xFFFFFFFFLL;
    ull b1 = b >> 32;
    /**
     * The point of the 4 lines above is to make
     *      a = a0 + ( a1 << 32 );
     *      b = b0 + ( b1 << 32 );
     * Now expand
     *      a * b = ( a0 + ( a1 << 32 ) )
     *            * ( b0 + ( b1 << 32 ) )
     * into 4 terms and evaluate each one modulo n.
     * The assumption here is that a, b and n are only
     * slightly bigger than ( 1 << 32 ).
     **/

    // The a0 * b0 term
    ull ans = ( a0 * b0 ) % n;

    // The a0 * b1 * 2^32 term  [ = ( a0 * ( 2^32 - 1 ) + a0 ) * b1 ]
    ans += ( ( ( ( a0 * 0xFFFFFFFFLL ) % n ) + a0 ) * b1 ) % n;

    // The a1 * 2^32 * b0 term  [ = ( b0 * ( 2^32 - 1 ) + b0 ) * a1 ]
    ans += ( ( ( ( b0 * 0xFFFFFFFFLL ) % n ) + b0 ) * a1 ) % n;

    // The a1 * b1 * 2^64 term  [ = ( ( 2^64 - 1 ) + 1 ) * a1 * b1  ]
    ans += ( ( ( ( ( ( ull )0xFFFFFFFFFFFFFFFFLL % n ) + 1 ) * a1 ) % n ) * b1 ) % n;

    return ans % n;
}

ull powmod( ull b, ull p, ull m )
{
    ull r = 1;
    for( ull i = ( ( ull )1 << 63 ); i; i >>= 1 )
    {
        r = multmod( r, r, m );
        if( p & i ) r = multmod( r, b, m );
    }
    return r;
}