#include <bits/stdc++.h>
using namespace std;
ifstream fin("input.txt");
ofstream fout("output.txt");
bool isPrime(long long int x) {
  if (x <= 4 || x % 2 == 0 || x % 3 == 0) return x == 2 || x == 3;
  for (int i = 5; i * i <= x; i += 6)
    if (x % i == 0 || x % (i + 2) == 0) return 0;
  return 1;
}
void primeFactors(long long n, set<long long> &Fac) {
  while (n % 2 == 0) {
    Fac.insert(2);
    n = n / 2;
  }
  for (int i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      Fac.insert(i);
      n = n / i;
    }
  }
  if (n > 2) Fac.insert(n);
}
int NumDigits(int x) {
  return (
      x < 10
          ? 1
          : (x < 100
                 ? 2
                 : (x < 1000
                        ? 3
                        : (x < 10000
                               ? 4
                               : (x < 100000
                                      ? 5
                                      : (x < 1000000
                                             ? 6
                                             : (x < 10000000
                                                    ? 7
                                                    : (x < 100000000
                                                           ? 8
                                                           : (x < 1000000000
                                                                  ? 9
                                                                  : 10)))))))));
}
inline void boostIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout.precision(10);
}
long long int Pow10[19] = {
    (long long int)0,    (long long int)1e1,  (long long int)1e2,
    (long long int)1e3,  (long long int)1e4,  (long long int)1e5,
    (long long int)1e6,  (long long int)1e7,  (long long int)1e8,
    (long long int)1e9,  (long long int)1e10, (long long int)1e11,
    (long long int)1e12, (long long int)1e13, (long long int)1e14,
    (long long int)1e15, (long long int)1e16, (long long int)1e17,
    (long long int)1e18};
long long int gcd(long long int a, long long int b) {
  return b ? gcd(b, a % b) : a;
}
long long int lcm(long long int a, long long int b) {
  return a * b / gcd(a, b);
}
long long MOD = 1e9 + 7;
template <class T>
struct Fenwick {
  vector<T> V;
  Fenwick(long long n) : V(n) {}
  void add(size_t i, T x) {
    for (; i < V.size(); i |= i + 1) V[i] += x;
  }
  T sum(long long i) {
    T r = T();
    for (--i; i >= 0; i = (i & (i + 1)) - 1) r += V[i];
    return r;
  }
  T sum(long long l, long long r) { return sum(r) - sum(l); }
};
long long f_Minimum(long long a, long long b) { return (min(a, b)); }
long long f_Maximum(long long a, long long b) { return (max(a, b)); }
long long f_Summarize(long long a, long long b) { return (a + b); }
class Parameter {
 public:
  long long InitialValue;
  long long (*Function)(long long a, long long b);
  Parameter(long long (*f)(long long a, long long b), long long value) {
    Function = f;
    InitialValue = value;
  }

 private:
};
Parameter Minimum(f_Minimum, LONG_LONG_MAX);
Parameter Maximum(f_Maximum, LONG_LONG_MIN);
Parameter Summarize(f_Summarize, 0);
class SegmentTree {
 public:
  SegmentTree(long long size, Parameter p) {
    Function = p.Function;
    InitialValue = p.InitialValue;
    n = size;
    data = vector<long long>(2 * n, 0);
  }
  SegmentTree(vector<long long> array, Parameter p) {
    Function = p.Function;
    InitialValue = p.InitialValue;
    n = array.size();
    ;
    data = vector<long long>(2 * n, 0);
    for (long long i = 0; i < (n); ++i) {
      data[n + i] = array[i];
    }
    for (long long i = n - 1; i >= 1; ++i) {
      data[i] = Function(data[i * 2], data[i * 2] + 1);
    }
  }
  void Update(long long idx, long long value) {
    idx += n;
    data[idx] = value;
    while (idx > 1) {
      idx /= 2;
      data[idx] = Function(data[idx * 2], data[idx * 2 + 1]);
    }
  }
  long long Find(long long left, long long right) {
    left += n;
    right += n;
    long long value = InitialValue;
    while (left < right) {
      if (left % 2 == 1) {
        value = Function(left, value);
        left++;
      }
      if (right % 2 == 1) {
        value = Function(right, value);
        right--;
      }
      left /= 2;
      right /= 2;
    }
    return value;
  }

 private:
  long long n;
  vector<long long> data;
  long long (*Function)(long long a, long long b);
  long long InitialValue;
};
int32_t main() {
  boostIO();
  vector<long long> A(0);
  long long in;
  cin >> in;
  while (in != 0) {
    A.push_back(in % 10);
    in /= 10;
  }
  reverse(A.begin(), A.end());
  vector<long long> ans(12, 1);
  long long n = A.size();
  for (long long i = 0; i < (n); ++i) {
    ans[11] *= A[i];
  }
  for (long long i = 0; i < (n); ++i) {
    vector<long long> B = A;
    if (B[i] == 0) {
      continue;
    }
    B[i]--;
    for (long long j = i + 1; j < n; ++j) {
      B[j] = 9;
    }
    for (long long j = 0; j < (n); ++j) {
      if (j == 0 && B[j] == 0) continue;
      ans[i] *= B[j];
    }
  }
  long long MAX = INT_MIN;
  for (long long i = 0; i < (12); ++i) {
    MAX = max(MAX, ans[i]);
  }
  cout << MAX << '\n';
  cerr << '\n' << "RUNTIME: " << 1.0 * clock() / CLOCKS_PER_SEC << " s" << '\n';
  return 0;
  ;
}

### Prompt

Your challenge is to write 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;
ifstream fin("input.txt");
ofstream fout("output.txt");
bool isPrime(long long int x) {
  if (x <= 4 || x % 2 == 0 || x % 3 == 0) return x == 2 || x == 3;
  for (int i = 5; i * i <= x; i += 6)
    if (x % i == 0 || x % (i + 2) == 0) return 0;
  return 1;
}
void primeFactors(long long n, set<long long> &Fac) {
  while (n % 2 == 0) {
    Fac.insert(2);
    n = n / 2;
  }
  for (int i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      Fac.insert(i);
      n = n / i;
    }
  }
  if (n > 2) Fac.insert(n);
}
int NumDigits(int x) {
  return (
      x < 10
          ? 1
          : (x < 100
                 ? 2
                 : (x < 1000
                        ? 3
                        : (x < 10000
                               ? 4
                               : (x < 100000
                                      ? 5
                                      : (x < 1000000
                                             ? 6
                                             : (x < 10000000
                                                    ? 7
                                                    : (x < 100000000
                                                           ? 8
                                                           : (x < 1000000000
                                                                  ? 9
                                                                  : 10)))))))));
}
inline void boostIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout.precision(10);
}
long long int Pow10[19] = {
    (long long int)0,    (long long int)1e1,  (long long int)1e2,
    (long long int)1e3,  (long long int)1e4,  (long long int)1e5,
    (long long int)1e6,  (long long int)1e7,  (long long int)1e8,
    (long long int)1e9,  (long long int)1e10, (long long int)1e11,
    (long long int)1e12, (long long int)1e13, (long long int)1e14,
    (long long int)1e15, (long long int)1e16, (long long int)1e17,
    (long long int)1e18};
long long int gcd(long long int a, long long int b) {
  return b ? gcd(b, a % b) : a;
}
long long int lcm(long long int a, long long int b) {
  return a * b / gcd(a, b);
}
long long MOD = 1e9 + 7;
template <class T>
struct Fenwick {
  vector<T> V;
  Fenwick(long long n) : V(n) {}
  void add(size_t i, T x) {
    for (; i < V.size(); i |= i + 1) V[i] += x;
  }
  T sum(long long i) {
    T r = T();
    for (--i; i >= 0; i = (i & (i + 1)) - 1) r += V[i];
    return r;
  }
  T sum(long long l, long long r) { return sum(r) - sum(l); }
};
long long f_Minimum(long long a, long long b) { return (min(a, b)); }
long long f_Maximum(long long a, long long b) { return (max(a, b)); }
long long f_Summarize(long long a, long long b) { return (a + b); }
class Parameter {
 public:
  long long InitialValue;
  long long (*Function)(long long a, long long b);
  Parameter(long long (*f)(long long a, long long b), long long value) {
    Function = f;
    InitialValue = value;
  }

 private:
};
Parameter Minimum(f_Minimum, LONG_LONG_MAX);
Parameter Maximum(f_Maximum, LONG_LONG_MIN);
Parameter Summarize(f_Summarize, 0);
class SegmentTree {
 public:
  SegmentTree(long long size, Parameter p) {
    Function = p.Function;
    InitialValue = p.InitialValue;
    n = size;
    data = vector<long long>(2 * n, 0);
  }
  SegmentTree(vector<long long> array, Parameter p) {
    Function = p.Function;
    InitialValue = p.InitialValue;
    n = array.size();
    ;
    data = vector<long long>(2 * n, 0);
    for (long long i = 0; i < (n); ++i) {
      data[n + i] = array[i];
    }
    for (long long i = n - 1; i >= 1; ++i) {
      data[i] = Function(data[i * 2], data[i * 2] + 1);
    }
  }
  void Update(long long idx, long long value) {
    idx += n;
    data[idx] = value;
    while (idx > 1) {
      idx /= 2;
      data[idx] = Function(data[idx * 2], data[idx * 2 + 1]);
    }
  }
  long long Find(long long left, long long right) {
    left += n;
    right += n;
    long long value = InitialValue;
    while (left < right) {
      if (left % 2 == 1) {
        value = Function(left, value);
        left++;
      }
      if (right % 2 == 1) {
        value = Function(right, value);
        right--;
      }
      left /= 2;
      right /= 2;
    }
    return value;
  }

 private:
  long long n;
  vector<long long> data;
  long long (*Function)(long long a, long long b);
  long long InitialValue;
};
int32_t main() {
  boostIO();
  vector<long long> A(0);
  long long in;
  cin >> in;
  while (in != 0) {
    A.push_back(in % 10);
    in /= 10;
  }
  reverse(A.begin(), A.end());
  vector<long long> ans(12, 1);
  long long n = A.size();
  for (long long i = 0; i < (n); ++i) {
    ans[11] *= A[i];
  }
  for (long long i = 0; i < (n); ++i) {
    vector<long long> B = A;
    if (B[i] == 0) {
      continue;
    }
    B[i]--;
    for (long long j = i + 1; j < n; ++j) {
      B[j] = 9;
    }
    for (long long j = 0; j < (n); ++j) {
      if (j == 0 && B[j] == 0) continue;
      ans[i] *= B[j];
    }
  }
  long long MAX = INT_MIN;
  for (long long i = 0; i < (12); ++i) {
    MAX = max(MAX, ans[i]);
  }
  cout << MAX << '\n';
  cerr << '\n' << "RUNTIME: " << 1.0 * clock() / CLOCKS_PER_SEC << " s" << '\n';
  return 0;
  ;
}

```