Polynomial Quine

Time limit0.5sMemory limit1024 MB

Summary

Given N, list all degree N-1 polynomials whose coefficients a_i lie in [0, N) and satisfy f(i) mod N = a_i for every i from 0 to N-1.

Level: Medium7 of 10
Topics: Math, Number theory
Solved: No attempts yet

Problem

An integer-coefficient polynomial $f(x) = a\_{N-1}x^{N-1} + \cdots + a\_1x + a\_0$ is called an $(N-1)$ -degree polynomial quine if it satisfies both of the following conditions.

For every integer $i$ with $0 ≤ i < N$ , $0 ≤ a\_i < N$ .
For every integer $i$ with $0 ≤ i < N$ , $f(i) \equiv a\_i \pmod N$ .

Surprisingly, for $1 ≤ N ≤ 200$ , there are exactly $N$ polynomial quines of degree $N-1$ .

Given $N$ , write a program that finds all $(N-1)$ -degree polynomial quines.

Input

The first line contains one integer $N$ ( $1 ≤ N ≤ 200$ ).

Output

Print $N$ lines, one polynomial quine per line. Print the coefficients from $a\_{N-1}$ down to $a\_0$ , separated by single spaces. Do not print the same polynomial more than once.

Print the polynomials in ascending order of $a\_{N-1}$ . If $a\_{N-1}$ ties, sort by $a\_{N-2}$ in ascending order, and so on. If $a\_{N-1}$ through $a\_1$ all tie, sort by $a\_0$ in ascending order.

Examples4

Example 1
Input
```
1
```
Expected output
```
0
```
Example 2
Input
```
2
```
Expected output
```
0 0
1 0
```
Example 3
Input
```
3
```
Expected output
```
0 0 0
1 2 2
2 1 1
```
Example 4
Input
```
4
```
Expected output
```
0 0 0 0
0 2 0 2
2 1 2 1
2 3 2 3
```