Micro has got an internship at a well reputed company. But something started bothering him when he joined. It's been one month now and he's still not able to figure out what it is. But he did a lot of research and has finally found a way to know what that something is. During his research he took an array A of size N, initialized with value 0 and performed Q operations on it. In one operation he added a value V to all A[i] (where X ≤ i ≤ Y). Now the something that's bothering him is sum of all S(C), where C is a subsequence of the array A and S(C) is the sum of all the elements in the subsequence C. Help Micro find out this. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

You will be provided with six integer values: a, b, c, d, e, f. The i^{th} operation is defined by three values X_i, Y_i, V_i, that means add V_i to all A[k], where X_i ≤ k ≤ Y_i. Now these values are to be generated using the following formulas:

$X_i = ((X_{i-1} \times a) + b)$\%N + 1; X_0 = 0

$Y_i = ((Y_{i-1} \times c) + d)$\%N + 1; Y_0 = 0

If X_i > Y_i: Swap(X_i, Y_i)

$V_i = ((V_{i-1} \times e) + f)$\%10^9 + 1; V_0 = 0

Input:
First line of input consists of a single integer T denoting the number of test cases.
First line of each test case consists of two space separated integers denoting N and Q.
Second line of each test case consists of six space separated integers denoting a, b, c, d, e, f.

Output:
Print the answer to each test case in a new line. As the answer can be large print it modulo 10^9+7.

Constraints:
1 ≤ T ≤ 10
1 ≤ N, Q, a, b, c, d, e, f ≤ 10^6

SAMPLE INPUT
1
3 3
1 1 1 1 1 1

SAMPLE OUTPUT
48

Explanation

The 3 operations will be
X_1 = 2, Y_1 = 2, V_1 = 2
X_2 = 1, Y_2 = 1, V_2 = 4
X_3 = 3, Y_3 = 3, V_3 = 6
So the array will be A[] = {4, 2, 6}
All subsequences, C and the value of function S(C) will be
C = {4} ;S(C) = 4
C = {2} ;S(C) = 2
C = {6} ;S(C) = 6
C = {4, 2} ;S(C) = 6
C = {4, 6} ;S(C) = 10
C = {2, 6} ;S(C) = 8
C = {4, 2, 6} ;S(C) = 12
So sum all values of S(C) is 48

见题面

见题面