Juno Puzzle for May
All submissions for this problem are available.
Chef Juno's girlfriend, May, is a programmer and a mathematician, and she loves solving problems. Everyday Chef Juno comes up with new problems for her to solve, otherwise she gets bored and depressed. He doesn't want her to feel so, but he has run out of all problems. He consults his Chef friends, who came up with a new problem.
The Chef City is an N-dimensional city of dimensions L*..*L[N-1] and each of the (L*..*L[N-1]) cells may have 0 to V-1 restaurants. They want to know the number of ways they can open restaurants in each cell of the city such that the sum of the number of restaurants in every sub-block(see details) in Chef City is divisible by V.
Chef Juno realizes that this number could be very huge given the size of Chef City, so to make this problem a little easier for his girlfriend (and for himself, as he should himself know the solution ;)), he wants the answer modulo 1000000007. But before asking her this problem, he wants to know the answer himself. So he turns to you for help. Please help him :)
A sub-block of an N-dimensional hyperrectangle can be defined as an N-dimensional hyperrectangle of
1*1*..L[i]..*1*1 dimensions for i ranging from 0 to N-1, where the ith dimension is L[i].
For example, in a 2*3*2 cuboid, we can have sub-blocks of
2*1*1, 1*3*1 and 1*1*2 dimensions and each of the 12 cells can have
0 to V-1 restaurants in such a way that the sum of the number of restaurants in every sub-block is divisible by V.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers V and N.
Since the input file size may go large, we ask you to generate the input using the following scheme.
You have two lines of 6 integers each.
The first line consists of the integers P, P, A0, B0, C0, M0.
The second line consists of the integers Q, Q, A1, B1, C1, M1.
Using the above, you can generate arrays P and Q as follows:
P[i] = A0 * A0 * P[i-1] + B0 * P[i-2] + C0 modulo (M0)
Q[i] = A1 * A1 * Q[i-1] + B1 * Q[i-2] + C1 modulo (M1)
for i>=2 and i < N
From this, the ith dimension can be calculated as follows:
The ith dimension, L[i] = P[i]*(M1)+Q[i]+1 for i>=0 and i < N
For each test case, output a single line containing the answer. As was mentioned above, you should print this number modulo 1000000007.
1 <= T <= 100000
2 <= N <= 100
1 <= V <= 2^63 - 1
0 <= P, P < max(10^5+1, M0)
0 <= Q, Q < max(10^5+1, M1)
1<=M0 and M1<=2^31-1
All N dimensions after calculation will be between 1 and 2^63 – 1.
Input: 3 1 2 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 2 2 1 1 1 1 1 3 3 1 1 1 1 1 2 1 1 0 0 0 2 Output: 1 729 387420489
Test case 1: Since V is equal to 1, there is only way to open restaurants in the 2 dimensional city of dimensions 3*3:
| 0 0 0 |
| 0 0 0 |
| 0 0 0 |
Here the sum of the number of restaurants opened in every sub-block of dimensions 1*3 and 3*1
is divisible by 1.
Test case 2: Here the dimensions of the city are 4*3 and V=3.
So one of the ways to open restaurants in each cell of the
|1 0 2|
|2 1 0|
|1 2 0|
|2 0 1|
Here the sum of the number of restaurants opened in every sub-block of dimensions 1*3 and 4*1
is divisible by V=3.
Test case 3: Here we are given a 3-dimensional hyperrectangle
of dimensions 4*4*3 and V is 3.
So in each of the 48 cells, we can open 0 to 2 restaurants, but we have to ensure that sum of the number of restaurants in every 4*1*1 sub-block, 1*4*1 sub-block and 1*1*3 sub-block is divisible by 3.
|Tags||exponentiation, may13, medium, mischievous_me, number-theory, simple-math|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.