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 \le n \le 2\cdot10^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\cdot8\cdot9=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$).

Difficulty: interview

Starter code:

Solutions:
n = int(input())
def p(x):
    ans = 1
    while x > 0:
        ans *= x % 10
        x //= 10
    return ans
ans = p(n)
for i in range(len(str(n))):
    cans = 9 ** i * p((n // 10 ** i) - 1)
    ans = max(ans, cans)
print(ans)


from sys import setrecursionlimit
setrecursionlimit(10**9)

def check(a):
    ans = 1
    a = int(a)
    while (a):
        ans *= a % 10
        a //= 10
    return ans

def ans(a, b, cnt):
    max_right = 0
    ans_right = 0
    max_mid = 0
    ans_mid = 0
    x = 9**(cnt)
    ans_right = b + (cnt) * '9'
    max_right = check(ans_right)
    a = int(a)
    b = int(b)
    while (a % 10 != 9):
        a += 1
    while (b % 10 != 9):
        b -= 1
    if (a > b):
        return max_right, ans_right
    a = str(a)
    b = str(b)
    a = (len(b) - len(a)) * '0' + a
    if (a != b and len(a) > 1):
        max_mid, ans_mid = ans(a[:-1], b[:-1], cnt + 1)
    else:
        ans_mid = b + '9'*(cnt)
        max_mid = check(ans_mid)
    if (max_right > max_mid):
        return max_right, ans_right
    return max_mid, ans_mid

mass_b = [1]

def get(a, b):
    nonlocal mass_b
    a = str(a)
    b = str(b)
    a = (len(b) - len(a)) * '0' + a
    for i in b:
        mass_b.append(mass_b[-1] * int(i))
        
    return int(ans(a, b, 0)[1])

def main():
    a = input()
    print(check(get(1, a)))

main()

x=int(input())
    
def numDigits(r):
    m=str(r)
    return len(m)
    
def prodDigits(r):
    m=str(r)
    k=1
    for i in range(len(m)):
        k*=int(m[i])
    return k

l=[]
for i in range(numDigits(x)):
    l.append(prodDigits(x))
    l.append(prodDigits(x-(x%(10**i))-1))
print(max(l))

def pd(d):
    d = str(d)
    ans = 1
    for c in d:
        ans *= int(c)
    return ans
        

S = input()
D = int(S)
ans = pd(D)

if str(D)[0] == '1':
    ans = 9 ** (len(str(D)) - 1)
else:
    cur = 0
    while 10 ** cur < D:
        ans = max(ans, pd(D - (D % 10 ** cur) - 1))
        
        cur += 1 
        
print(ans)


n = int(input())

sn = str(n)
k = len(sn)


ans = 1
for i in sn:
    ans *= int(i)

for i in range(k-1):
    n -= (10 ** (i+1))
    n //= (10 ** (i+1))
    n *= (10 ** (i+1))
    n += (10 ** (i+1)) - 1
    if (n < 0):
        break
    sn = str(n)
    res = 1
    for i in sn:
        res *= int(i)
    ans = max(res, ans)
    #print(n)

print(ans)


def s(a):
    a=list(a)
    while a and a[0]=='0':
        a.pop(0)
    prod=1 
    for i in a:
        
        prod*=int(i)
    return prod 
a=input()
ans=[s(a),a]
for i in range(len(a)-1, -1, -1):
    if a[i]=='0':continue
    b=a[:i] + str(int(a[i])-1) + "9"*len(a[i+1:])
    if s(b) > ans[0]:
        ans=[s(b),b]
print(int(ans[0]))

def f(x):
    if x[0]=='1':
        return 9**(len(x)-1)
    elif len(x)==1:
        return int(x)
    else:
        return max((int(x[0])-1)*9**(len(x)-1),int(x[0])*f(x[1:]))
n=input('')
print(f(n))


def multi(nu):
	r = 1
	for x in str(nu):
		r *= int(x)
	return r

n = int(input())
res = multi(n)
for i in range(100):
	aa = n-(n%(10**i))-1
	if aa >= 0:
		res = max(res, multi(aa))
print(res)


def f(l):
    n = len(l)
    if n == 1:
        return l[0]
    
    nn = pow(9, n - 1)
    res = nn

    for i in range(1, l[0]):
        res = max(res, i * nn)
    res = max(l[0] * f(l[1:]), res)
    return res

x = [*map(int, input())]
print(f(x))

from collections import defaultdict
import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER
@atexit.register
def write():
    sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())

n = list(input())
c = 0
t = 1
for i in range(len(n)):
    j = int(n[i])
    t2 = t*(j-1)
    t = t*j
    c = max(t2*((9)**(len(n)-i-1)) , c)
    if i==0 and t2==0:
        c = max(((9)**(len(n)-i-1)) , c)
        
        
c = max(t,c)
print(c)
                


n=input()
q=len(n)-1
ma=9**q
q=1
for i in range(len(n)):
    if n[i]!='0':
        e=q
        e*=(int(n[i])-1)
        e*=9**(len(n)-i-1)
        ma=max(ma, e)
    q *= int(n[i])
w=1
for i in n:
    w*=int(i)
print(max(ma, w))

from sys import stdin,stdout
from collections import defaultdict,Counter,deque
from bisect import bisect,bisect_left
import math
from itertools import permutations 
import queue




def sumOfDigits(x) :  
      
    prod = 1
    while (x) : 
        prod *= (x % 10)  
        x //= 10;  
      
    return prod 
# Returns the maximum number 
# with maximum sum of digits. 
def findMax(x) : 
      
    
    b = 1
    ans = x 
      
    
    while (x!=0) : 
        
        cur = (x - 1) * b + (b - 1) 
          
        
        if (sumOfDigits(cur) > sumOfDigits(ans) or
        (sumOfDigits(cur) == sumOfDigits(ans) and
            cur > ans)) : 
                ans = cur 
  
        # reduces the number 
        # to one unit less 
        x =x // 10
        b = b * 10
      
      
    return ans 




#stdin = open('input.txt','r')
I = stdin.readline
n = int(I())

ans = findMax(n)
prod = 1
for i in str(ans):
	prod*=(int(i))
print(prod)


def mp():
    return map(int, input().split())

def f(x):
    r = 1
    for i in str(x):
        r *= int(i)
    return r

n = int(input())
r = f(n)
l = len(str(n))

for i in range(l):
    s = str(n)
    k = int(s[:i] + str(max(0, int(s[i]) - 1)) + '9' * (l - i - 1))
    r = max(r, f(k))
    
print(r)

n = input()

mx = 9 ** int((len(n) - 1))
if len(n) == 1:
    print(n)
    return
cnt = 1
for i in n:
    cnt *= int(i)
if cnt > mx:
    mx = cnt
for i in range(len(n)):
    cur = n

    if cur[i] != "0":
        cur = cur[:i] + str(int(cur[i]) - 1) + "9" * (len(n) - i - 1)
    cnt = 1


    for j in cur:
        cnt *= int(j)
    if cnt > mx:
        mx = cnt

print(mx)


def calc(n):
    ret=1
    while n != 0:
        ret *= (n % 10)
        n //= 10
    return ret

def solve():
    n=int(input())
    ans=calc(n)
    for i in range(1,10):
        a=(n+1)%(10**i)
        if n<a:
            break
        ans=max(ans,calc(n-a))
    return ans

print(solve())


s = input()
def chuj(st,le):
	if le == 1:
		return int(st)
	return max(max((int(st[0])-1),1) * 9**(le-1), int(st[0]) * chuj(st[1:], le - 1))
print(chuj(s,len(s)))

from collections import defaultdict as dd
import math
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))

n=li()

digits=[int(i) for i in n]

ma=0
prod=1
for j in digits:
	prod=prod*j

ma=max(ma,prod)



for i in range(1,len(digits)):
	#print(digits)
	if not digits[~i]==0:
		digits[~i]-=1
		j=1

		while i-j>=0:	
			digits[~(i-j)]=9
			j+=1
	else:
		continue

	prod=1
	#print(digits)
	for j in range(len(digits)):
		if not (j==0 and digits[j]==0):
			prod=prod*digits[j]
		

	ma=max(ma,prod)
	

	
print(ma)







n = int(input())

def get_p(n):
    if n == 0: return 0
    p = 1
    while n > 0:
        p *= n % 10
        n //= 10

    return p

mx = get_p(n)
d = 10
nn = n
while d <= n:
    nn -= d
    nn = nn - (nn % d) + (d - 1)
    mx = max(get_p(nn), mx)

    d *= 10

print(mx)


def foo(nums):
    res = 1
    flag = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            flag = 1
        if flag:
            res *= nums[i]
    return res


nums = list(map(int, list(input())))
res = foo(nums)
for i in range(len(nums)):
    nums2 = nums[:i]
    if nums[i] != 0:
        nums2.append(nums[i] - 1)
        for j in range(len(nums) - i - 1):
            nums2.append(9)
        res = max(res, foo(nums2))

print(res)


a = list(input())
c = 0
t = 1
for i in range(len(a)):
    j = int(a[i])
    t2 = t*(j-1)
    t = t*j
    c = max(t2*((9)**(len(a)-i-1)) , c)
    if i==0 and t2==0:
        c = max(((9)**(len(a)-i-1)) , c)

c = max(t,c)
print(c)


n = list(map(int, input()))

m = 1

for i, d in enumerate(reversed(n)):
    if i == 0:
        m = d
    else:
        m = max(d*m, (max(d-1, 1))*(9**i))
print(m)