Kurt reaches nirvana when he finds the product of all the digits of some positive integer. Greater value of the product makes the nirvana deeper.

Help Kurt find the maximum possible product of digits among all integers from 1 to n.

Input

The only input line contains the integer n (1 ≤ n ≤ 2⋅10^9).

Output

Print the maximum product of digits among all integers from 1 to n.

Examples

Input


390


Output


216


Input


7


Output


7


Input


1000000000


Output


387420489

Note

In the first example the maximum product is achieved for 389 (the product of digits is 3⋅8⋅9=216).

In the second example the maximum product is achieved for 7 (the product of digits is 7).

In the third example the maximum product is achieved for 999999999 (the product of digits is 9^9=387420489).
'''
Basically we want to find maximum product of digits we could
get from number 1 to n. To be precise there must be a number
in the range 1 to n which could generate this maximum product.
So then from this number we will print the product.

So basically we would like to find digits which could lead us
to maximum product.

To find the digits we could use following recursion formula:

1. f(n) = max(f(n // 10) * (n % 10), f((n // 10) - 1) * 9), 
when n >= 10
2. f(n) = max(1, n), when n < 10

Basically the first formula tell us that if we want to find
digit which lead to maximum product, we could search it one
of two conditions:

- search in current set of digit, for example if we have n = 123
the digit could be in 120..123 (0..3)
- take 9 from previous set of digit, for example if we have n = 123
we take 9 from previous set of digit which is 119, the reason why we
take 9 is because it is the only digit which guarantee the product
of digit would be maximum (since it is the maximum digit)

After the current digit found, we search on another digit using the
function again (recursive)
'''

def f(n):
    if (n < 10):
        return max(1, n)
    return max(f(n // 10) * (n % 10), f((n // 10) - 1) * 9)

n = int(input())
print(f(n))
