Greatest Product

Time limit1sMemory limit128 MB

Summary

Given N up to two billion, find the largest product of digits over all integers from 1 to N.

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

Problem

September 10th is Forest Day. To celebrate, the dwellers of the Magic Forest decided to throw a party, and Kuzma the beaver was put in charge of the intellectual games. The rules of the game Kuzma invented are simple.

The host announces a positive integer $N$ . For every positive integer from $1$ to $N$ , the player computes the product of that integer's digits, and must report the greatest such product.

To run the game smoothly, all answers must be known in advance. This is tricky because $N$ can be fairly large ( $1 \le N \le 2000000000$ ). Since Kuzma is not comfortable with computers, write a program that, given a positive integer $N$ , finds the correct answer.

In other words, over all integers $k$ with $1 \le k \le N$ , output the maximum possible product of the digits of $k$ .

Input

Each line of the input contains one integer $N$ . The input may span several lines until end of file (EOF). ( $1 \le N \le 2000000000$ )

Output

For each $N$ , print on the corresponding line the greatest digit product among the integers from $1$ to $N$ .

Examples5

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
101090000
```
Expected output
```
43046721
```
Example 3
Input
```
28994
```
Expected output
```
10368
```
Example 4
Input
```
4876
```
Expected output
```
2268
```
Example 5
Input
```
2789
```
Expected output
```
1008
```