### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### PREREQUISITES

Math, Repeated Squaring, Fermat’s Little Theorem

### PROBLEM

You are given a **N** dimensional hyper rectangle. You have to fill each cell in the hyper rectangle with a value between **0** and **V-1**, inclusive, such that the sum of all the values in each **1-dimensional slice** of the hyper rectangle is divisible by **V**, which is also given.

Find the number of ways of filling the cells with the values.

### QUICK EXPLANATION

Let the dimensions of the hyper rectangle be given in an array D = { D_{1}, D_{2}, … D_{N} }.

Assume we fill the each of the following cells of the hyper rectangle with any arbitrary value from 0 to V-1 of our choosing

- Fill { x
_{1}, x_{2}, … x_{N}} iff- x
_{1}< D_{1}AND - x
_{2}< D_{2}AND - so on…

- x

The rest of the cells that have not been filled can only be filled by singular values that satisfy the divisibility constraint.

Take for example a hyper-rectangle { 4, 4, 3 } and V = 10. Suppose we fill all the cells as described above arbitrarily. There are of course 10^{3*3*2} ways of filling them. Now, when we take any slice of this hyper-rectangle, we find that

- Either the cell is filled by a value of our choosing
- The value of the cell is being forced by some or the other 1-dimensional slice

All except one value in each slice will be pre-filled or forced, and the last value is of course being forced by the constraint that the sum of all the values in this slice must be divisible by V.

Thus, the answer for each case is going to be

V^{(D1-1)(D2-1)…(DN-1)}

### EXPLANATION

V is a 64-bit integer. But we want to find the result modulo 1000000007. Thus, we can instantly change V to the remainder modulo 1000000007.

Given that each of the dimensions are 64-bit integers, it is obvious that the exponent of V for the answer is potentially very large. It is potentially a 6400-bit integer. Repeated squaring to find the result of V^{6400-bit-integer} will take 6400 iterations. This is too many iterations per test case.

We require Fermat’s Little Theorem to solve the problem now.

a^{p-1}= 1 modulo p for some prime p

We know that 1000000007 is prime. Thus we can find

T = (D_{1}- 1)(D_{2}- 1) ... (D_{N}- 1) modulo 1000000006

and find V^{T} modulo 1000000007.

There is one edge case that deserves special mention. V modulo 1000000007 may or may not be 0. If it is not 0, then we have no problems. But if it is 0 there is a special case that should be carefully handled. This is the case where one or more dimension is equal to 1. In this case, all the values in the hyper rectangle must be 0. This is because every cell is a single dimensional slice in a dimension that is equal to 1. Thus the answer in that case should be 1, instead of 0 (meaning the answer is actually 1, and not a multiple of 1000000007).

Of course, as evil as the setter and the tester are, there is no shortage of this case among the judge test cases.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.