#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
 
enum {
    MAX = ~0ull,
    base = 1ull << 32
};
 
uint64_t clamp_mul(uint64_t a, uint64_t b)
{
    if (MAX / a < b) return MAX;
 
    return a * b;
}
 
uint64_t mod_mul(uint64_t a, uint64_t b)
{
    uint64_t a1 = a / base;
    uint64_t a0 = a % base;
    uint64_t b1 = b / base;
    uint64_t b0 = b % base;
 
    uint64_t lo = a0 * b0;
    uint64_t hi = clamp_mul(a1, b0) % base
                + clamp_mul(a0, b1) % base
                + lo / base;
 
    return (hi % base) * base + (lo % base);
}
 
uint64_t stdc_mul(uint64_t a, uint64_t b)
{
    return a * b;
}
 
void roll(unsigned n, uint64_t a, uint64_t x, 
    uint64_t (*mul)(uint64_t a, uint64_t b))
{
    while (n-- ) {
        x = mul(x, a);
 
        printf("%lu\n", x);
    }
 
    puts("");
}
 
 
int main(void)
{
    uint64_t a = 1181783497276652981ull;
    uint64_t x = 1000000000;
 
    unsigned n = 10;
 
    puts("Matlab:");    roll(n, a, x, clamp_mul);
    puts("Std C");      roll(n, a, x, stdc_mul);
    puts("Modulo");     roll(n, a, x, mod_mul);
 
    return 0;
}
 

I2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHN0ZGludC5oPgoKZW51bSB7CiAgICBNQVggPSB+MHVsbCwKICAgIGJhc2UgPSAxdWxsIDw8IDMyCn07Cgp1aW50NjRfdCBjbGFtcF9tdWwodWludDY0X3QgYSwgdWludDY0X3QgYikKewogICAgaWYgKE1BWCAvIGEgPCBiKSByZXR1cm4gTUFYOwogICAgCiAgICByZXR1cm4gYSAqIGI7Cn0KCnVpbnQ2NF90IG1vZF9tdWwodWludDY0X3QgYSwgdWludDY0X3QgYikKewogICAgdWludDY0X3QgYTEgPSBhIC8gYmFzZTsKICAgIHVpbnQ2NF90IGEwID0gYSAlIGJhc2U7CiAgICB1aW50NjRfdCBiMSA9IGIgLyBiYXNlOwogICAgdWludDY0X3QgYjAgPSBiICUgYmFzZTsKICAgIAogICAgdWludDY0X3QgbG8gPSBhMCAqIGIwOwogICAgdWludDY0X3QgaGkgPSBjbGFtcF9tdWwoYTEsIGIwKSAlIGJhc2UKICAgICAgICAgICAgICAgICsgY2xhbXBfbXVsKGEwLCBiMSkgJSBiYXNlCiAgICAgICAgICAgICAgICArIGxvIC8gYmFzZTsKICAgICAgICAgICAgICAgIAogICAgcmV0dXJuIChoaSAlIGJhc2UpICogYmFzZSArIChsbyAlIGJhc2UpOwp9Cgp1aW50NjRfdCBzdGRjX211bCh1aW50NjRfdCBhLCB1aW50NjRfdCBiKQp7CiAgICByZXR1cm4gYSAqIGI7Cn0KCnZvaWQgcm9sbCh1bnNpZ25lZCBuLCB1aW50NjRfdCBhLCB1aW50NjRfdCB4LCAKICAgIHVpbnQ2NF90ICgqbXVsKSh1aW50NjRfdCBhLCB1aW50NjRfdCBiKSkKewogICAgd2hpbGUgKG4tLSApIHsKICAgICAgICB4ID0gbXVsKHgsIGEpOwogICAgICAgIAogICAgICAgIHByaW50ZigiJWx1XG4iLCB4KTsKICAgIH0KICAgIAogICAgcHV0cygiIik7Cn0KCgppbnQgbWFpbih2b2lkKQp7CiAgICB1aW50NjRfdCBhID0gMTE4MTc4MzQ5NzI3NjY1Mjk4MXVsbDsKICAgIHVpbnQ2NF90IHggPSAxMDAwMDAwMDAwOwogICAgCiAgICB1bnNpZ25lZCBuID0gMTA7CiAgICAKICAgIHB1dHMoIk1hdGxhYjoiKTsgICAgcm9sbChuLCBhLCB4LCBjbGFtcF9tdWwpOwogICAgcHV0cygiU3RkIEMiKTsgICAgICByb2xsKG4sIGEsIHgsIHN0ZGNfbXVsKTsKICAgIHB1dHMoIk1vZHVsbyIpOyAgICAgcm9sbChuLCBhLCB4LCBtb2RfbXVsKTsKICAgIAogICAgcmV0dXJuIDA7Cn0K