NNN-numbers

Time limit1sMemory limit1024 MB

Summary

Given N, list all N-digit base-N numbers where each digit equals how many times its position's digit value appears, in increasing order.

Level: Medium6 of 10
Topics: Backtracking, Math, Implementation
Solved: No attempts yet

Problem

We are used to writing numbers in decimal. When we write 123, it actually stands for $1 \cdot 10^2 + 2 \cdot 10 + 3$ .

In general, a base- $N$ number uses digits from $0$ to $N-1$ , and $abc$ stands for $a \cdot N^2 + b \cdot N + c$ . When $N > 10$ , the digits after $9$ are uppercase Latin letters in ASCII order (A = 10, B = 11, $\dots$ , Z = 35). For example, the base-16 number F1 stands for $15 \cdot 16 + 1$ , which is $241$ in decimal.

An $N$ -digit NNN-number is a base- $N$ number with exactly $N$ digits in which the units digit equals the number of times digit 1 appears in it, the tens digit equals the number of times digit 2 appears, and so on. The leftmost digit equals the number of zeros in the number.

Input

The only line of the text file contains a decimal integer $N$ ( $2 \le N \le 36$ ).

Output

Write all $N$ -digit NNN-numbers to the text file in increasing order, one per line. If there are none, the only line of the file contains EI OLE.

Examples2

Example 1
Input
```
5
```
Expected output
```
20021
```
Example 2
Input
```
2
```
Expected output
```
EI OLE
```