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≠ 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)mod 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)mod 5=2, the distance from 3 to 1 is dist(3,1)=(1-3+5)mod 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,…,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 ≤ n ≤ 5⋅ 10^6) — the number of robots playing this game.

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

Each of the next m line contains four integers p_i, k_i, b_i, w_i (1 ≤ p_i ≤ n, 1 ≤ k_i ≤ 10^9+7, 0 ≤ b_i ,w_i< k_i). It's guaranteed that p_m=n and p_{j-1}<p_{j} (2 ≤ j ≤ 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( ∏_{i=1}^{n} ((ans_i ⊕ i^2)+1)\right) mod 10^9+7, where ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

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 ⊕ 1^2)+1)×((5 ⊕ 2^2)+1)×((0 ⊕ 3^2)+1)) mod 10^9+7=(5× 2 × 10)mod 10^9+7=100.

Difficulty: VERY_HARD
Tags: Complete search

Data structures

Implementation

Greedy algorithms
Skill types: Complete search

Data structures

Greedy algorithms

Starter code:

Solutions: