One night, while sitting around a campfire, Rory Mercury tells a strange story from a long time ago…

Legend tells of a legendary graph with N vertices numbered from 1 to N and no edges. Each of its vertices had an interval [Pi, Qi] associated with. The intervals might have represented something meaningful long ago, but the meaning has been long forgotten. The graph existed for a total of T years, with a major event occurring at the end of every year of its existence. At the end of the i^th year, the graph either grew an edge from Ui to Vi or asked itself a question in an attempt to gain some self-identity and graduate from being just another abstract mathematical object. The questions it asks itself are in the form "What is the sum of lengths of the intersections between an interval [Xi, Yi] and every vertex in my connected component containing the vertex Zi?" Recall that the intersection of two intervals is the longest interval that is contained within both intervals. If the intervals are disjoint then the length of the intersection is zero, otherwise the length of an interval [L, R] is equal to R - L + 1 (we use "number of integers" as the length of an interval instead of the standard definition).

Rory then described each of the T events in great detail. There are so many events that you almost fell asleep. To stay awake, you decide to reproduce the answers to the questions of the graph.

Input Format:
The first line of input will contain two integers N and T.
The second line of input will contain five integers A, B, C, D, and E, the initial state of a pseudorandom number generator.
The function randInt will return a pseudorandom number, modifying the state of the generator in the process. Watch out for integer overflow when you implement it.

function randInt(MIN, MAX):
F = (A * C + B * D + E) modulo 1,000,000,007
A = B
B = F
return ( F modulo (MAX - MIN + 1) ) + MIN

The intervals of the vertices of the graph are given by this pseudocode:
for i from 1 to N, inclusive:
P = randInt(1, 1,000,000)
Q = randInt(P, 1,000,000)
the interval of vertex i is [P, Q]

After the intervals of the vertices of the graph are determined, the events are described by this pseudocode:
for i from 1 to T, inclusive:
if randInt(1, 2) is equal to 1:
U = randInt(1, N)
V = randInt(1, N)
event i is that the graph grows an edge from U to V
else:
X = randInt(1, 1,000,000)
Y = randInt(X, 1,000,000)
Z = randInt(1, N)
event i is that the graph asks the question with the interval [X, Y] and vertex Z
Note: It is important that you execute the code sequentially, generating the queries after the intervals, because randInt will modify the state of the pseudorandom generator. It follows that you should not call randInt outside of the generator code before you finish generating all the input.

Output Format:
Let answer be the sum of i * vali over all i from 1 to T, inclusive, where vali is the answer to the question the graph asked itself, if it asked one, otherwise it is 0. Output answer modulo 10^9+7.

Constraints:
1 ≤ N ≤ 10^6
1 ≤ T ≤ 3 × 10^6
1 ≤ Pi ≤ Qi ≤ 10^6
1 ≤ Xi ≤ Yi ≤ 10^6
1 ≤ Ui, Vi, Zi ≤ N
0 ≤ A, B, C, D, E < 10^9+7

SAMPLE INPUT
20 25
1 2 3 4 5

SAMPLE OUTPUT
73387766

Explanation

Here are the correct values of the generator and the answers to the questions. Note that the sample input may not be very useful to debug your solution on due to the large and random values.

P1 = 17, Q1 = 92
P2 = 354, Q2 = 1996
P3 = 7633, Q3 = 43092
P4 = 164738, Q4 = 930068
P5 = 555537, Q5 = 628508
P6 = 739170, Q6 = 955122
P7 = 261898, Q7 = 287841
P8 = 109133, Q8 = 127921
P9 = 43772, Q9 = 163527
P10 = 980757, Q10 = 981199
P11 = 182599, Q11 = 528249
P12 = 190293, Q12 = 780808
P13 = 543095, Q13 = 776958
P14 = 235311, Q14 = 551568
P15 = 288943, Q15 = 619689
P16 = 238868, Q16 = 562185
P17 = 654537, Q17 = 978281
P18 = 250007, Q18 = 966593
P19 = 609305, Q19 = 849427
P20 = 154568, Q20 = 715924

event 1 is a grow event: U1 = 8, V1 = 14
event 2 is a question event: X2 = 861828, Y2 = 952669, Z2 = 4
event 3 is a grow event: U3 = 5, V3 = 2
event 4 is a grow event: U4 = 19, V4 = 9
event 5 is a question event: X5 = 495670, Y5 = 923276, Z5 = 11
event 6 is a question event: X6 = 470996, Y6 = 847307, Z6 = 20
event 7 is a question event: X7 = 332590, Y7 = 350288, Z7 = 19
event 8 is a question event: X8 = 835836, Y8 = 956430, Z8 = 19
event 9 is a grow event: U9 = 5, V9 = 18
event 10 is a grow event: U10 = 2, V10 = 12
event 11 is a question event: X11 = 180886, Y11 = 720572, Z11 = 11
event 12 is a grow event: U12 = 7, V12 = 16
event 13 is a grow event: U13 = 12, V13 = 9
event 14 is a grow event: U14 = 13, V14 = 14
event 15 is a question event: X15 = 401440, Y15 = 654179, Z15 = 19
event 16 is a question event: X16 = 57969, Y16 = 573047, Z16 = 4
event 17 is a question event: X17 = 496283, Y17 = 519411, Z17 = 2
event 18 is a grow event: U18 = 2, V18 = 9
event 19 is a grow event: U19 = 16, V19 = 1
event 20 is a grow event: U20 = 6, V20 = 18
event 21 is a grow event: U21 = 18, V21 = 8
event 22 is a question event: X22 = 859374, Y22 = 941997, Z22 = 8
event 23 is a question event: X23 = 137037, Y23 = 414289, Z23 = 15
event 24 is a grow event: U24 = 8, V24 = 9
event 25 is a question event: X25 = 81050, Y25 = 720752,
Z25 = 12

val1 = 0
val2 = 68241
val3 = 0
val4 = 0
val5 = 32580
val6 = 244929
val7 = 0
val8 = 13592
val9 = 0
val10 = 0
val11 = 345651
val12 = 0
val13 = 0
val14 = 0
val15 = 623327
val16 = 408310
val17 = 46258
val18 = 0
val19 = 0
val20 = 0
val21 = 0
val22 = 165248
val23 = 125347
val24 = 0
val25 = 1780809

见题面

见题面