Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Qingshan and Daniel

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputQingshan 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$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/19/2021 14:54:21 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|