You are now in a supermarket and notice that a promotion is being held. The promotional device consists of lights arranged in rows, with two lights in each row.

Each time, you press the button for every row. For the -th row:

• If light is on, you gain points.
•  If light is on, you gain points.

Each row has an associated probability , where:

• Light is on with probability .
• Light  is on with probability .

For one round of the event, your total score is defined as the product of the points obtained from all rows.

There is also a random button. After pressing it, rows are chosen at random. In each of those selected rows, the two lights are swapped (that is, if light is on, you gain points; if light is on, you gain points).

You want to determine whether pressing this random button can improve your expected points. Therefore, you decide to compute the expected value of your final points after pressing the random button modulo .

The first line contains two integers  and  ().

Each of the next  lines contains four integers  (), where the probability that light  is on is .

Output a single integer representing the expected score after pressing the random button, modulo .

Let the expected value be a rational number , where  and  are integers and .

You should output: , where  denotes the modular multiplicative inverse of  modulo .

2 1
1 2 1 2
2 1 1 2

748683267

For Example 1, after pressing the random button, either the two lights in the first row or the two lights in the second row will be swapped, each with a probability of . In the case where the first row is swapped, the expected score is . In the case where the second row is swapped, the expected score is also . Therefore, the total expected score is . When taken modulo , the output is .

4 2
11 4 5 6
5 14 3 4
19 19 5 10
8 10 6 11

84459925

4 2
10 0 1 2
0 10 1 2
11 4 3 4
3 4 4 11

283592800