#include <iostream>
typedef unsigned long long BIG;
BIG mod_multiply( BIG A, BIG B, BIG C )
{
BIG mod_product = 0;
// A %= C; may or may not help performance
B %= C;
while (A) {
if (A & 1) {
mod_product += B;
if (mod_product > C) mod_product -= C;
}
A >>= 1;
B <<= 1;
if (B > C) B -= C;
}
return mod_product;
}
int main()
{
uint64_t retval = mod_multiply( 19010000000000000000, 1011000000000000, 1231231231231211 );
std::cout << retval << "\n";
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgQklHOwpCSUcgbW9kX211bHRpcGx5KCBCSUcgQSwgQklHIEIsIEJJRyBDICkKewogICAgQklHIG1vZF9wcm9kdWN0ID0gMDsKICAgIC8vIEEgJT0gQzsgbWF5IG9yIG1heSBub3QgaGVscCBwZXJmb3JtYW5jZQogICAgQiAlPSBDOwoKICAgIHdoaWxlIChBKSB7CiAgICAgICAgaWYgKEEgJiAxKSB7CiAgICAgICAgICAgIG1vZF9wcm9kdWN0ICs9IEI7CiAgICAgICAgICAgIGlmIChtb2RfcHJvZHVjdCA+IEMpIG1vZF9wcm9kdWN0IC09IEM7CiAgICAgICAgfQogICAgICAgIEEgPj49IDE7CiAgICAgICAgQiA8PD0gMTsKICAgICAgICBpZiAoQiA+IEMpIEIgLT0gQzsKICAgIH0KCiAgICByZXR1cm4gbW9kX3Byb2R1Y3Q7Cn0KCmludCBtYWluKCkKewogICAgdWludDY0X3QgcmV0dmFsID0gbW9kX211bHRpcGx5KCAxOTAxMDAwMDAwMDAwMDAwMDAwMCwgMTAxMTAwMDAwMDAwMDAwMCwgMTIzMTIzMTIzMTIzMTIxMSApOwogICAgc3RkOjpjb3V0IDw8IHJldHZhbCA8PCAiXG4iOwp9