Nirvana【思维+暴力优化】

Nirvana

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 11 to nn.

Input

The only input line contains the integer nn (1≤n≤2⋅1091≤n≤2⋅109).

Output

Print the maximum product of digits among all integers from 11 to nn.

Examples

Input

Output

Input

Output

Input

1000000000

Output

387420489

Note

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

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

In the third example the maximum product is achieved for 999999999999999999 (the product of digits is 99=38742048999=387420489).

题意：

给出一个小于2e9的正整数n 要求找到从1~n 中的一个数满足它的每位数相乘结果最大并输出该结果

思路：

开始肯定是想直接暴力从1~n 但明显会超时

对于每个输入的数n 例如：390

先考虑把他-1 变成389 然后再-1 变成388 、387 仔细想想根本不需要减那么多次因为389 各位相乘肯定大于 388

同理4099 先-100 变成3999 再-100变成3899 也没必要所以总结规律如下：

从数n的最后一位开始通过向前一位借1的方法每次都把最后一位变成9 （最大值对应的数肯定会出现在这些情况里面）

例如：

390 --> 389 --> 299 --> 99

(99可以不考虑，因为前面的299 肯定大于 199)

最后把每一种情况对应的值都计算出来取最大的

AC代码：

#include<stdio.h>
typedef long long LL;
LL sum(LL n)
{
    LL num=n,count2=0;
    char a[15];
    while(num){
        LL num1=num%10;
        num/=10;
        a[count2++]=num1+'0';
    }
    LL sum2=1;
    for(int i=count2-1;i>=0;i--){
        sum2=sum2*(a[i]-'0');
    }
    return sum2;
}
int main()
{
    LL c[15]={0,1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000};
    LL n;
    scanf("%lld",&n);
    LL maxx=sum(n),j=1;
    while(n>=0){
        while((n/c[j])%10!=9&&n>=0){
            n-=c[j];
        }
        LL num2=sum(n);
        if(num2>maxx){
            maxx=num2;
        }
        j++;
    }
    printf("%lld
",maxx);
    return 0;
}