#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
template <typename X>
inline X abs(const X& a) {
  return a < 0 ? -a : a;
}
template <typename X>
inline X sqr(const X& a) {
  return a * a;
}
const int size = 1e5 + 5;
const double eps = 0.0001;
const long double PI = 3.1415926535897932384626433832795;
const long long MOD = 1000000007;
const long long INF = 1LL << 62;
const long long MAX5 = 100001;
const long long MAX6 = 1000001;
const long long MAX17 = 99999999999999999;
const double DMAX = 2e18 + 5;
const int P = 239017;
void solution();
void include_file();
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solution();
  return 0;
}
inline void include_file() {
  ios_base::sync_with_stdio(true);
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
inline bool isPrime(long long n) {
  for (int i = 2; i * i <= n; ++i)
    if (n % i == 0) return false;
  return true;
}
inline string ekv(string a) {
  if (a.size() & 1) return a;
  string x = ekv(a.substr(0, a.size() / 2));
  string y = ekv(a.substr(a.size() / 2));
  return min(x + y, y + x);
}
inline long long cubic_root(long long x) {
  long long l = 0, r = MAX6;
  while (l != r) {
    long long m = (l + r + 1) / 2;
    if (m * m * m > x)
      r = m - 1;
    else
      l = m;
  }
  return l;
}
inline float FastInvSqrt(float x) {
  float xhalf = 0.5f * x;
  int i = *(int*)&x;
  i = 0x5f3759df - (i >> 1);
  x = *(float*)&i;
  x = x * (1.5f - (xhalf * x * x));
  return x;
}
inline long long gcd(long long a, long long b) {
  while (b ^= a ^= b ^= a = a % b)
    ;
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
unsigned long long NCR(unsigned long long n, unsigned long long r) {
  if (r == 0) return 1;
  if (r > n >> 1) return NCR(n, n - r);
  unsigned long long res = 1;
  for (long long k = 1; k <= r; ++k) {
    res *= (unsigned long long)(n - k + 1);
    res /= k;
  }
  return res;
}
constexpr uint64_t mod = (1ull << 61) - 1;
inline uint64_t modmul(uint64_t a, uint64_t b) {
  uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
  uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
  uint64_t ret =
      (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
  ret = (ret & mod) + (ret >> 61);
  ret = (ret & mod) + (ret >> 61);
  return ret - 1;
}
void yes() { cout << "YES"; }
void no() { cout << "NO"; }
void yes(bool res, bool small = false) {
  if (!small) {
    if (res)
      cout << "YES";
    else
      cout << "NO";
  } else {
    if (res)
      cout << "Yes";
    else
      cout << "No";
  }
}
void dabl(double x) { printf("%.10lf", x); }
namespace bits {
template <typename X>
inline X MAX(const X& a, const X& b) {
  return b & ((a - b) >> 31) | a & (~(a - b) >> 31);
}
template <typename X>
inline X MIN(const X& a, const X& b) {
  return a & ((a - b) >> 31) | b & (~(a - b) >> 31);
}
inline bool check2(const long long n) { return n > 0 && (n & (n - 1)); }
inline long long ostatok2(const long long n, const long long m) {
  return m & (n - 1);
}
template <typename X>
inline void SWAP(X& a, X& b) {
  a ^= b;
  b ^= a;
  a ^= b;
}
inline size_t count_1_in_LL(unsigned long long n) {
  std::size_t i(0);
  for (; n; ++i) n &= n - 1;
  return i;
}
}  // namespace bits
void debug() { cout << endl; }
template <typename H, typename... T>
void debug(H p, T... t) {
  std::cout << p << " ";
  debug(t...);
}
vector<vector<int> > g;
inline void solution() {
  string s;
  cin >> s;
  int n = s.size();
  if (n == 1)
    cout << s;
  else {
    long long res = 0;
    for (long long i = 0; i < n; ++i) {
      if (s[i] > '1') {
        string tmp = s;
        tmp[i]--;
        for (long long j = i + 1; j < n; ++j) tmp[j] = '9';
        long long cur = 1;
        for (long long i = 0; i < n; ++i) cur *= (tmp[i] - '0');
        res = max(res, cur);
      }
    }
    long long cur = 1;
    for (long long i = 0; i < n; ++i) cur *= (s[i] - '0');
    res = max(res, cur);
    if (s[0] == '1') {
      res = 1;
      for (long long i = 1; i < n; ++i) res *= 9;
    };
    cout << res;
    ;
  }
}

### Prompt

Develop a solution in cpp to the problem described below:

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>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
template <typename X>
inline X abs(const X& a) {
  return a < 0 ? -a : a;
}
template <typename X>
inline X sqr(const X& a) {
  return a * a;
}
const int size = 1e5 + 5;
const double eps = 0.0001;
const long double PI = 3.1415926535897932384626433832795;
const long long MOD = 1000000007;
const long long INF = 1LL << 62;
const long long MAX5 = 100001;
const long long MAX6 = 1000001;
const long long MAX17 = 99999999999999999;
const double DMAX = 2e18 + 5;
const int P = 239017;
void solution();
void include_file();
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solution();
  return 0;
}
inline void include_file() {
  ios_base::sync_with_stdio(true);
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
inline bool isPrime(long long n) {
  for (int i = 2; i * i <= n; ++i)
    if (n % i == 0) return false;
  return true;
}
inline string ekv(string a) {
  if (a.size() & 1) return a;
  string x = ekv(a.substr(0, a.size() / 2));
  string y = ekv(a.substr(a.size() / 2));
  return min(x + y, y + x);
}
inline long long cubic_root(long long x) {
  long long l = 0, r = MAX6;
  while (l != r) {
    long long m = (l + r + 1) / 2;
    if (m * m * m > x)
      r = m - 1;
    else
      l = m;
  }
  return l;
}
inline float FastInvSqrt(float x) {
  float xhalf = 0.5f * x;
  int i = *(int*)&x;
  i = 0x5f3759df - (i >> 1);
  x = *(float*)&i;
  x = x * (1.5f - (xhalf * x * x));
  return x;
}
inline long long gcd(long long a, long long b) {
  while (b ^= a ^= b ^= a = a % b)
    ;
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
unsigned long long NCR(unsigned long long n, unsigned long long r) {
  if (r == 0) return 1;
  if (r > n >> 1) return NCR(n, n - r);
  unsigned long long res = 1;
  for (long long k = 1; k <= r; ++k) {
    res *= (unsigned long long)(n - k + 1);
    res /= k;
  }
  return res;
}
constexpr uint64_t mod = (1ull << 61) - 1;
inline uint64_t modmul(uint64_t a, uint64_t b) {
  uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
  uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
  uint64_t ret =
      (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
  ret = (ret & mod) + (ret >> 61);
  ret = (ret & mod) + (ret >> 61);
  return ret - 1;
}
void yes() { cout << "YES"; }
void no() { cout << "NO"; }
void yes(bool res, bool small = false) {
  if (!small) {
    if (res)
      cout << "YES";
    else
      cout << "NO";
  } else {
    if (res)
      cout << "Yes";
    else
      cout << "No";
  }
}
void dabl(double x) { printf("%.10lf", x); }
namespace bits {
template <typename X>
inline X MAX(const X& a, const X& b) {
  return b & ((a - b) >> 31) | a & (~(a - b) >> 31);
}
template <typename X>
inline X MIN(const X& a, const X& b) {
  return a & ((a - b) >> 31) | b & (~(a - b) >> 31);
}
inline bool check2(const long long n) { return n > 0 && (n & (n - 1)); }
inline long long ostatok2(const long long n, const long long m) {
  return m & (n - 1);
}
template <typename X>
inline void SWAP(X& a, X& b) {
  a ^= b;
  b ^= a;
  a ^= b;
}
inline size_t count_1_in_LL(unsigned long long n) {
  std::size_t i(0);
  for (; n; ++i) n &= n - 1;
  return i;
}
}  // namespace bits
void debug() { cout << endl; }
template <typename H, typename... T>
void debug(H p, T... t) {
  std::cout << p << " ";
  debug(t...);
}
vector<vector<int> > g;
inline void solution() {
  string s;
  cin >> s;
  int n = s.size();
  if (n == 1)
    cout << s;
  else {
    long long res = 0;
    for (long long i = 0; i < n; ++i) {
      if (s[i] > '1') {
        string tmp = s;
        tmp[i]--;
        for (long long j = i + 1; j < n; ++j) tmp[j] = '9';
        long long cur = 1;
        for (long long i = 0; i < n; ++i) cur *= (tmp[i] - '0');
        res = max(res, cur);
      }
    }
    long long cur = 1;
    for (long long i = 0; i < n; ++i) cur *= (s[i] - '0');
    res = max(res, cur);
    if (s[0] == '1') {
      res = 1;
      for (long long i = 1; i < n; ++i) res *= 9;
    };
    cout << res;
    ;
  }
}

```