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).
# Python3 Program to find the number  
# in a range having maximum product  
# of the digits  
  
# Returns the product of digits 
# of number x  
def product(x) :  
      
    prod = 1
    while (x) : 
        prod *= (x % 10)  
        x //= 10;  
      
    return prod 
  
# This function returns the number having  
# maximum product of the digits  
def findNumber(l, r) : 
  
    # Converting both integers to strings  
    a = str(l);  
    b = str(r);  
  
    # Let the current answer be r  
    ans = r 
    b=list(b)
    for i in range(len(b)) :  
        if (b[i] == '0') :  
            continue
  
        # Stores the current number having  
        # current digit one less than current  
        # digit in b  
        curr = list(b) 
        #curr[i] = str(((ord(curr[i]) - 
        #                ord('0')) - 1) + ord('0')) 
    
        curr[i]=str(int(curr[i])-1)
        
        # Replace all following digits with 9  
        # to maximise the product  
        for j in range(i + 1, len(curr)) : 
            curr[j] = '9' 
              
        # Convert string to number  
        num = 0
        #for c in curr : 
        #    num = num * 10 + (int(c) - ord('0'))  
        num=int(''.join(curr))
        # Check if it lies in range and its 
        # product is greater than max product  
        if (num >= l and product(ans) < product(num)) : 
            ans = num 

    return ans
  
# Driver Code  
if __name__ == "__main__" : 
    r=int(input())
    l= 1
    if r<10:
        print(r)
    else:
        print(product(findNumber(l, r)))