Суммы по столбцам огромной матрицы без промахов кеша

Матрица n × m генерируется по строкам генератором: x₀ = seed, x_{k+1} = (x_k · 1103515245 + 12345) mod 2³¹, а элемент очередной клетки равен x_{k+1} >> 16 (целочисленный сдвиг). Клетки заполняются по строкам: (0,0), (0,1), …, (0,m−1), (1,0), ….

Посчитайте суммы S_j по каждому столбцу и выведите H = XOR по j от 0 до m−1 значений (S_j · (j + 1)) mod (10⁹ + 7).

Ввод: n, m, seed (1 ≤ n, m ≤ 4000, 0 ≤ seed < 2³¹).

Вывод: число H.

Ограничение по времени 2 секунды.

Пример 1

Ввод:

2 3 1

Вывод:

74199

Пример 2

Ввод:

1 1 0

Вывод:

0