# Programming contests

## ECN programozó csapatverseny, 2017. május 13.

May 13, 2017 10:10 AM – May 13, 2017 3:10 PM

# Cube

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.

## Input Specification

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).

## Output Specification

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.

1. `1`
2. `2`

## Output for Sample Input 1

1. `23`

## Explanation of Sample Input 1

We have a single case, use two colors, e.g., black and white. Cases:

• 1 case using 8 white unit cubes;
• 1 case using 7 white unit cubes and 1 black unit cube;
• 3 cases using 6 white unit cubes and 2 black unit cubes;
• 3 cases using 5 white unit cubes and 3 black unit cubes;
• 7 cases using 4 white unit cubes and 4 black unit cubes;
• 3 cases using 3 white unit cubes and 5 black unit cubes;
• 3 cases using 2 white unit cubes and 6 black unit cubes;
• 1 case using 1 white unit cube and 7 black unit cubes;
• 1 case using 8 black unit cubes;

Total: 23 different colorings.

## Sample Input 2

1. `4`
2. `2`
3. `1000`
4. `5000`
5. `2000000000`

## Output for Sample Input 2

1. `23`
2. `45538`
3. `280943`
4. `185532`