408970: GYM103399 C Fast modular multiplication modulo 63-bit modulus

You are to complete the following snippet of code:

#include <iostream>

using namespace std;

struct state
{
    unsigned a, b, c, d;
};

uint32_t xorshift128(state& s)
{
    uint32_t bk = s.d;
    uint32_t ft = s.a;
    s.d = s.c;
    s.c = s.b;
    s.b = s.a;
    bk ^= bk << 11;
    bk ^= bk >> 8;
    return s.a = bk ^ ft ^ (ft >> 19);
}

uint64_t xorshift128ll(state& s)
{
    uint64_t l = xorshift128(s);
    uint64_t r = xorshift128(s);
    return l << 32 | r;
}

struct test
{
    uint64_t x, y, modulo;
};

const uint32_t BITS = 63;

test xorshift128_test(state& s)
{
    test t;
    t.x = xorshift128ll(s) & ((1ll << BITS) - 1);
    t.y = xorshift128ll(s) & ((1ll << BITS) - 1);
    t.modulo = xorshift128ll(s) & ((1ll << BITS) - 1) | (1ll << (BITS - 1));
    if (t.x >= t.modulo)
        t.x -= t.modulo;
    if (t.y >= t.modulo)
        t.y -= t.modulo;
    return t;
}

uint64_t prod(const test& t)
{
    // TODO
}

int main()
{
    int n;
    state s;
    cin >> n >> s.a >> s.b >> s.c >> s.d;
    uint64_t ans = 0;
    for (int i = 0; i < n; ++i)
        ans += prod(xorshift128_test(s));
    cout << ans << endl;
}

Replace «// TODO» with body of the function calculating the product of two 63-bit integers t.x and t.y modulo 63-bit integer t.modulo.

The first line contains a single integer $$$n$$$ — the number of the modular multiplication tests ($$$1 \leqslant n \leqslant 3\cdot 10^7$$$).

The second line contains four integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ — the initial state of xorshift pseudorandom number generator ($$$0 \leqslant a,b,c,d \leqslant 2^{32}-1$$$).

Output the sum of products of t.x and t.y modulo t.modulo, taken modulo $$$2^{64}$$$.

1
1 2 3 4

1134850256585927726