Square
Source: National Olympiad in Informatics, Romania 2005 (2nd day)
Author: Tiberiu Danet
A magic square of order N (1 <= N <= 1 000 000) is a matrix with 3 lines and 3 columns with non-negative integer elements that has the following property: the sum of the elements of any line or any column is N. Write a program that will determine the number of magic squares of order N modulo 30103.
Input
The input file patrat.in contains on the first line the natural number N.
Output
The output file patrat.out will contain the number of magic squares of order N modulo 30103.
Sample Input/Output
| patrat.in | patrat.out |
|---|---|
| 2 | 21 |
| patrat.in | patrat.out |
| 5 | 231 |