Factorial Digit Count

Time limit1sMemory limit128 MB

Summary

Given N, list every positive integer X for which X! has exactly N decimal digits, or report that none exists.

Level: Medium6 of 10
Topics: Math, Binary search, Number theory, Implementation
Solved: No attempts yet

Problem

Given a positive integer $N$ , find every positive integer $X$ such that $1 \times 2 \times 3 \times \cdots \times X$ (that is, $X!$ ) has exactly $N$ decimal digits. Such an $X$ may not exist. You may assume $1 \le N \le 150000$ .

Input

The first line of input contains a single positive integer $N$ .

Output

If no such $X$ exists, print the string NO on the first line. Otherwise, print on the first line how many values of $X$ satisfy the condition, then print all such $X$ in increasing order, one per line.

Examples4

Example 1
Input
```
5
```
Expected output
```
1
8
```
Example 2
Input
```
1
```
Expected output
```
3
1
2
3
```
Example 3
Input
```
2
```
Expected output
```
1
4
```
Example 4
Input
```
3
```
Expected output
```
2
5
6
```