B. Nirvana（Codeforces Round #549 (Div. 2)）

B. 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 1 to n.

Input

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

Output

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

Examples

inputCopy

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 99=387420489).

题意：

给出一个数，算出这个数以内的最大的位数乘积值（比如：390 最大的乘积值是3⋅8⋅9=216）

讲解：

我的方法是将除个位数以外的全部数，从个位开始变成9，一直到这个位数的后一位变成9。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
long long cmp(long long a){
	long long sum=1;
	while(a!=0){
		sum*=a%10;
		a/=10;
	}
	return sum; 
}//算出位数乘积
long long cmp1(long long v){
	long long k=0;
	while(v!=0){
		k++;
		v/=10;
	}
	return k;
}//算出位数
int main(){
	 long long n;
	 while(cin>>n){
	 	if(n>0&&n<10){
	 		cout<<n<<endl;
	 		continue;
		}//个位不在考虑
		long long length=cmp1(n),qq,final=0,t,i;
		long long max=cmp(n);//考虑到原数是否为最大，将max的值变为原数的乘积值
		for(i=1;i<=length;i++){
			qq=pow(10,i);
			final=(n/qq-1)*qq+qq-1;//将一个数的从个位开始依次向前变成9，
			且变成9之前的数单独变成一个数并减一，再将这个数后面全变成9
			t=cmp(final);
			if(t>max){
				max=t;//比较出最大值
			}
		}
		cout<<max<<endl;
	 }
	return 0;
}