A. Быстрое умножение по 32-битному модулю
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам предложено дополнить следующий код:

#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 = 32;

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;
}

Напишите на месте «// TODO» функцию, находящую произведение 32-битных чисел t.x и t.y по 32-битному модулю t.modulo.

Входные данные

В первой строке находится целое число $$$n$$$ — количество тестов на умножение по модулю ($$$1 \leqslant n \leqslant 3\cdot 10^7$$$).

Во второй строке находится четыре целых числа $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$, разделённых пробелом — начальные параметры генератора псевдослучайных чисел xorshift ($$$0 \leqslant a,b,c,d \leqslant 2^{32}-1$$$).

Выходные данные

Выведите одно число — сумму всех произведений t.x и t.y по модулю t.modulo, взятую по модулю $$$2^{64}$$$.

Пример
Входные данные
1
1 2 3 4
Выходные данные
118481142