#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
string ds = "RLDU";
const int MAX = 1e5;
string to_string(char z) { return string(1, z); }
string to_string(bool a) { return a ? "true" : "false"; }
string to_string(const char* st) { return string(st); }
string to_string(string st) { return st; }
string to_string(vector<bool> vec) {
  {
    string res;
    for (int i = (0); i < (((int)vec.size())); i++) res += char('0' + vec[i]);
    return res;
  }
}
template <size_t S>
string to_string(bitset<S> bb) {
  string res;
  for (int i = (0); i < (S); i++) res += char('0' + bb[i]);
  return res;
}
template <class T>
string to_string(T v) {
  bool f = 1;
  string an;
  for (auto& x : v) {
    if (!f) an += ' ';
    f = 0;
    an += to_string(x);
  }
  return an;
}
void _Debug() { cout << "]" << endl; }
template <class H, class... T>
void _Debug(H h, T... t) {
  cout << to_string(h);
  if (sizeof...(t)) cout << ", ";
  _Debug(t...);
}
long long clc(long long n) {
  long long ans = 1;
  while (n) {
    ans *= (n % 10);
    n /= 10;
  }
  return ans;
}
void solve() {
  long long n;
  cin >> n;
  n++;
  long long best = 0, p = 1;
  while (n) {
    best = max(best, clc(n * p - 1));
    n /= 10, p *= 10;
  }
  cout << best << endl;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  for (int i = (1); i < (t + 1); i++) {
    solve();
  }
}

### Prompt

Generate a CPP solution to the following problem:

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).

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
string ds = "RLDU";
const int MAX = 1e5;
string to_string(char z) { return string(1, z); }
string to_string(bool a) { return a ? "true" : "false"; }
string to_string(const char* st) { return string(st); }
string to_string(string st) { return st; }
string to_string(vector<bool> vec) {
  {
    string res;
    for (int i = (0); i < (((int)vec.size())); i++) res += char('0' + vec[i]);
    return res;
  }
}
template <size_t S>
string to_string(bitset<S> bb) {
  string res;
  for (int i = (0); i < (S); i++) res += char('0' + bb[i]);
  return res;
}
template <class T>
string to_string(T v) {
  bool f = 1;
  string an;
  for (auto& x : v) {
    if (!f) an += ' ';
    f = 0;
    an += to_string(x);
  }
  return an;
}
void _Debug() { cout << "]" << endl; }
template <class H, class... T>
void _Debug(H h, T... t) {
  cout << to_string(h);
  if (sizeof...(t)) cout << ", ";
  _Debug(t...);
}
long long clc(long long n) {
  long long ans = 1;
  while (n) {
    ans *= (n % 10);
    n /= 10;
  }
  return ans;
}
void solve() {
  long long n;
  cin >> n;
  n++;
  long long best = 0, p = 1;
  while (n) {
    best = max(best, clc(n * p - 1));
    n /= 10, p *= 10;
  }
  cout << best << endl;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  for (int i = (1); i < (t + 1); i++) {
    solve();
  }
}

```