There is a regular n-gon. Some points are marked on each of its sides. There are x₁ point marked on the first side, x₂ – on the second, …, x_n – on the nth. The marked points do not coincide with the vertices of the n-gon. You can choose no more than one of the marked points from each side and form a convex non-degenerate polygon by connecting all those points with lines. Now your task is to find the number of different k-gons that can be formed that way.

Input

The first line of input file contains positive integer t – the amount of test cases. Next t lines contain six integers each: n, k, a, b, c, m. Here n is the number of sides of the initial n-gon. The amount of marked points on the first side of this n-gon is x₁ = a, the amount of the marked points on the following sides is x_i = (b*x_i-1 + c) mod m, for i > 1.

Constraints

1 <= t <= 30
3 <= n <= 10⁹
3 <= k <= 20
1 <= b, c, m <= 10⁶
0 <= a < m

Output

For each test case output the number of k-gons that can be formed modulo 1000000007.

Example

Input:
2
4 3 1 2 2 191
10 5 1 113 157 999991

Output:
1228
328836201