E. Qingshan and Daniel
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Qingshan and Daniel are going to play a card game. But it will be so boring if only two persons play this. So they will make $$$n$$$ robots in total to play this game automatically. Robots made by Qingshan belong to the team $$$1$$$, and robots made by Daniel belong to the team $$$2$$$. Robot $$$i$$$ belongs to team $$$t_i$$$. Before the game starts, $$$a_i$$$ cards are given for robot $$$i$$$.

The rules for this card game are simple:

  • Before the start, the robots are arranged in a circle in the order or their indices. The robots will discard cards in some order, in each step one robot discards a single card. When the game starts, robot $$$1$$$ will discard one of its cards. After that, robots will follow the following rules:
  • If robot $$$i$$$ discards the card last, the nearest robot whose team is opposite from $$$i$$$'s will discard the card next. In another word $$$j$$$ will discard a card right after $$$i$$$, if and only if among all $$$j$$$ that satisfy $$$t_i\ne t_j$$$, $$$dist(i,j)$$$ (definition is below) is minimum.
  • The robot who has no cards should quit the game immediately. This robot won't be considered in the next steps.
  • When no robot can discard the card next, the game ends.

We define the distance from robot $$$x$$$ to robot $$$y$$$ as $$$dist(x,y)=(y-x+n)\bmod n$$$. It is similar to the oriented distance on the circle.

For example, when $$$n=5$$$, the distance from $$$1$$$ to $$$3$$$ is $$$dist(1,3)=(3-1+5)\bmod 5=2$$$, the distance from $$$3$$$ to $$$1$$$ is $$$dist(3,1)=(1-3+5)\bmod 5 =3$$$.

Later, Qingshan finds out that it will take so much time to see how robots play. She wants to know the result as quickly as possible. You, as Qingshan's fan, are asked to calculate an array $$$[ans_1,ans_2,\ldots,ans_n]$$$ — $$$ans_i$$$ is equal to the number of cards, that $$$i$$$-th robot will discard during the game. You need to hurry!

To avoid the large size of the input, the team and the number of cards of each robot will be generated in your code with some auxiliary arrays.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 5\cdot 10^6$$$) — the number of robots playing this game.

The second line contains one integer $$$m$$$ ($$$1 \le m \le \min(n,200\,000)$$$).

Each of the next $$$m$$$ line contains four integers $$$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$$$). It's guaranteed that $$$p_m=n$$$ and $$$p_{j-1}<p_{j}$$$ ($$$2 \le j \le m$$$).

Arrays $$$a_j$$$ and $$$t_j$$$ should be generated by the following pseudo code:


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
Output

Print a single integer $$$\left( \prod_{i=1}^{n} ((ans_i \oplus i^2)+1)\right) \bmod 10^9+7$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.

Examples
Input
3
3
1 5 2 3
2 7 1 2
3 2 1 1
Output
100
Input
5000000
2
1919810 998244353 114514 19260817
5000000 233333333 623532 7175
Output
800210675
Input
1
1
1 1 0 0
Output
1
Note

In the first test case $$$a=[5,5,1]$$$ and $$$t=[1,2,2]$$$.

The robot $$$1$$$ discards the card first.

Then robot $$$2$$$ discards the card next. Robot $$$3$$$ doesn't discard the card next because $$$dist(1,2)<dist(1,3)$$$.

Then robot $$$1$$$ discards the card next. Robot $$$3$$$ doesn't discard the card next because $$$t_2=t_3$$$.

If we write down the index of the robot who discards a card in time order, it will be the sequence $$$[1,2,1,2,1,2,1,2]$$$. So robots $$$1$$$, $$$2$$$ and $$$3$$$ discard $$$5$$$, $$$5$$$ and $$$0$$$ cards, respectively. And the answer is $$$(((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$$$.