SP9448 SWARM - Swarm of Polygons

There is a regular n-gon. Some points are marked on each of its sides. There are x $ _{1} $ point marked on the first side, x $ _{2} $ – 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.

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 $ _{1} $ = a, the amount of the marked points on the following sides is x $ _{i} $ = (b\*x $ _{i-1} $ + c) mod m, for i > 1.

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