E. Циншань и Даниэль
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Циншань и Даниэль собираются сыграть в карточную игру. Но играть в нее только вдвоем будет очень скучно. Поэтому они решили сделать $$$n$$$ роботов, чтобы они сыграли в игру автоматически. Роботы, сделанные Циншань, относятся к команде $$$1$$$, а роботы, сделанные Даниэлем, относятся к команде $$$2$$$. Робот $$$i$$$ находится в команде $$$t_i$$$. Перед началом игры роботу $$$i$$$ выдается $$$a_i$$$ карт.

Правила карточной игры просты:

  • Роботы выстраиваются по кругу в порядке номеров и будут в некотором порядке выбрасывать по одной карте. Сначала робот $$$1$$$ выбрасывает одну из своих карт из игры. После этого роботы будут действовать по следующим правилам:
  • Если последнюю карту выбросил робот $$$i$$$, то следующим карту выбрасывает ближайший робот, чья команда противоположна команде $$$i$$$-го робота. Другими словами, робот $$$j$$$ должен выбросить одну свою карту сразу после робота $$$i$$$, если и только если среди всех возможных $$$j$$$ таких, что $$$t_i\ne t_j$$$, расстояние $$$dist(i,j)$$$ (определение будет дано ниже) минимально.
  • Робот, у которого больше не осталось карт, должен завершить игру немедленно. Этот робот не будет рассматриваться в следующих шагах.
  • Когда нет подходящего робота, который должен выбросить следующую карту, игра заканчивается.

Мы определяем расстояние от робота $$$x$$$ до робота $$$y$$$ как $$$dist(x,y)=(y-x+n)\bmod n$$$. Это соответствует ориентированному расстоянию по кругу.

Например, если $$$n=5$$$, то расстояние от $$$1$$$ до $$$3$$$ это $$$dist(1,3)=(3-1+5)\bmod 5=2$$$, а расстояние от $$$3$$$ до $$$1$$$ это $$$dist(3,1)=(1-3+5)\bmod 5 =3$$$.

Циншань заметила, что наблюдение за игрой роботов занимает очень большое время. Она хочет узнать результаты как можно быстрее. Вы, как фанат Циншань, должны помочь ей посчитать массив $$$[ans_1,ans_2,\ldots,ans_n]$$$: $$$ans_i$$$ равно количеству карт, которое выбросит $$$i$$$-й робот в течение всей игры. Нужно спешить!

Чтобы избежать большого размера входных данных, команды и количества карт каждого робота должны быть сгенерированы в вашей программе с использованием некоторых вспомогательных массивов.

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

В первой строке находится единственное целое число $$$n$$$ ($$$1 \le n \le 5\cdot 10^6$$$) — количество роботов, играющих в игру.

Во второй строке находится единственное целое число $$$m$$$ ($$$1 \le m \le \min(n,200\,000)$$$).

Каждая из следующих $$$m$$$ строк содержит четыре целых числа $$$p_i$$$, $$$k_i$$$, $$$b_i$$$, $$$w_i$$$ ($$$1 \le p_i \le n$$$, $$$1 \le k_i \le 10^9+7$$$, $$$0 \le b_i ,w_i< k_i$$$). Гарантируется, что $$$p_m=n$$$ и $$$p_{j-1}<p_{j}$$$ ($$$2 \le j \le m$$$).

Массивы $$$a_j$$$ и $$$t_j$$$ должны быть сгенерированы следующим псевдокодом:


seed = 0
base = 0

function rnd():
	ret = seed
	seed = (seed * base + 233) mod 1000000007
	return ret

p[0] = 0
for i = 1 to m:
	seed = b[i]
	base = w[i]
	for j = p[i - 1] + 1 to p[i]:
		t[j] = (rnd() mod 2) + 1
		a[j] = (rnd() mod k[i]) + 1
Выходные данные

Выведите единственное целое число $$$\left( \prod_{i=1}^{n} ((ans_i \oplus i^2)+1)\right) \bmod 10^9+7$$$, где $$$\oplus$$$ обозначает операцию исключающего ИЛИ.

Примеры
Входные данные
3
3
1 5 2 3
2 7 1 2
3 2 1 1
Выходные данные
100
Входные данные
5000000
2
1919810 998244353 114514 19260817
5000000 233333333 623532 7175
Выходные данные
800210675
Входные данные
1
1
1 1 0 0
Выходные данные
1
Примечание

В первом тесте $$$a=[5,5,1]$$$ и $$$t=[1,2,2]$$$.

Робот $$$1$$$ выбрасывает первую карту.

Затем робот $$$2$$$ выбрасывает карту. Это делает не робот $$$3$$$, потому что $$$dist(1,2)<dist(1,3)$$$.

Затем робот $$$1$$$ выбрасывает карту. Это делает не робот $$$3$$$, потому что $$$t_2=t_3$$$.

Если мы выпишем индексы роботов, которые будут выбрасывать карты по очереди, то мы получим последовательность $$$[1,2,1,2,1,2,1,2]$$$. Поэтому роботы $$$1$$$, $$$2$$$ и $$$3$$$ уберут $$$5$$$, $$$5$$$ и $$$0$$$ карт, соответственно. Ответ будет равен $$$(((5 \oplus 1^2)+1)\times((5 \oplus 2^2)+1)\times((0 \oplus 3^2)+1)) \bmod 10^9+7=(5\times 2 \times 10)\bmod 10^9+7=100$$$.