We have a number of monochrome unit cubes colored with n different colors (we have more of each color). Our target is to build with 8 randomly picked cubes as many differently colored 2 × 2 × 2 cubes as possible. Two cubes are considered identical if we can get it through rotating another construction, otherwise they are considered different colorings.
Example: having two colors, i.e., black and white unit cubes, we can build 23 differently colored 2 × 2 × 2 cubes.
Considering that there are enough cubes in n different colors, compute the number of differently colored 2 × 2 × 2 cubes that can be built using them.
On the first line of the input, we have the number C of test cases. Each of the next C lines contains a number n, the number of the different colors of the unit cubes (0 ≤ n ≤ 2 000 000 000).
The output will contain C lines, every line will contain the number of differently colored cubes modulo 666013 that can be obtained with n colors. The order of the numbers will correspond to the input lines' order.
Sample Input 1
Output for Sample Input 1
Explanation of Sample Input 1
We have a single case, use two colors, e.g., black and white. Cases:
Total: 23 different colorings.
Sample Input 2
Output for Sample Input 2
Explanation of Sample Input 2
We have four cases with 2, 1000, 5000, and 2 000 000 000 colors. Results modulo 666013 are: 23, 45538, 280943, and 185532.
|University of Debrecen; Faculty of Informatics; v. 03/01/2019|