#include <bits/stdc++.h>
using namespace std;
unsigned long long power(unsigned long long x, int y, int p) {
  unsigned long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
bool cmp(pair<string, int> &a, pair<string, int> &b) {
  return a.second < b.second;
}
void sort(map<string, int> &M) {
  vector<pair<string, int> > A;
  for (auto &it : M) {
    A.push_back(it);
  }
  sort(A.begin(), A.end(), cmp);
  for (auto &it : A) {
    cout << it.first << ' ' << it.second << endl;
  }
}
unsigned long long modInverse(unsigned long long n, int p) {
  return power(n, p - 2, p);
}
unsigned long long nCrModPFermat(unsigned long long n, int r, int p) {
  if (n < r) return 0;
  if (r == 0) return 1;
  unsigned long long fac[n + 1];
  fac[0] = 1;
  for (long long int i = 1; i <= n; i++) fac[i] = (fac[i - 1] * i) % p;
  return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) %
         p;
}
long long gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long int a, long long int b) { return (a / gcd(a, b)) * b; }
bool isPrime(long long int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
long long int fact(long long int n, long long int p) {
  return (n == 1 || n == 0) ? 1 : (n * (fact(n - 1, p)));
}
long long int nof(long long int n) {
  if (n == 1) {
    return 1;
  }
  long long int ans = 2;
  for (long long int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      if (i * i == n) {
        ans += 1;
      } else {
        ans += 2;
      }
    }
  }
  return ans;
}
long long int power(long long int num, long long int deg, long long int m) {
  if (!deg) return 1;
  if (deg % 2) {
    return (power(num, deg - 1, m) * num) % m;
  } else {
    long long int sqrt_res = power(num, deg / 2, m);
    return (sqrt_res * sqrt_res) % m;
  }
}
void seive(vector<long long int> &prm) {
  bool mark[102] = {false};
  long long int size = 102;
  mark[0] = true;
  mark[1] = true;
  for (long long int i = 2; i * i < size; i++) {
    if (mark[i] == false) {
      for (long long int j = i + i; j < size; j += i) {
        mark[j] = true;
      }
    }
  }
  for (long long int i = 0; i < 102; i++) {
    if (mark[i] == false) {
      prm.push_back(i);
    }
  }
}
bool stt(const pair<long long int, long long int> &a,
         const pair<long long int, long long int> &b) {
  return a.second < b.second;
}
long long int pp = 0;
void chk(vector<vector<long long int> > &cnt, long long int node,
         vector<long long int> &can, long long int tm, long long int mn) {
  if (can[node] == 0) {
    if (1) {
      if (cnt[node].size() != 2) {
        pp = 1;
        return;
      } else {
        return;
      }
    } else {
      return;
    }
  } else {
    return;
  }
  can[node] = 0;
  if (can[cnt[node][0]] == 1) {
    chk(cnt, cnt[node][0], can, tm + 1, mn);
    chk(cnt, cnt[node][1], can, tm + 1, mn);
  }
}
long long int calc(long long int n) {
  if (n / 10 == 0) {
    if (n == 0) {
      return 1;
    } else {
      return n;
    }
  }
  return max((n % 10 * calc(n / 10)), calc(n / 10 - 1) * 9);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int t = 1;
  while (t--) {
    long long int n;
    cin >> n;
    cout << calc(n);
  }
  return 0;
}

### 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>
using namespace std;
unsigned long long power(unsigned long long x, int y, int p) {
  unsigned long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
bool cmp(pair<string, int> &a, pair<string, int> &b) {
  return a.second < b.second;
}
void sort(map<string, int> &M) {
  vector<pair<string, int> > A;
  for (auto &it : M) {
    A.push_back(it);
  }
  sort(A.begin(), A.end(), cmp);
  for (auto &it : A) {
    cout << it.first << ' ' << it.second << endl;
  }
}
unsigned long long modInverse(unsigned long long n, int p) {
  return power(n, p - 2, p);
}
unsigned long long nCrModPFermat(unsigned long long n, int r, int p) {
  if (n < r) return 0;
  if (r == 0) return 1;
  unsigned long long fac[n + 1];
  fac[0] = 1;
  for (long long int i = 1; i <= n; i++) fac[i] = (fac[i - 1] * i) % p;
  return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) %
         p;
}
long long gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long int a, long long int b) { return (a / gcd(a, b)) * b; }
bool isPrime(long long int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
long long int fact(long long int n, long long int p) {
  return (n == 1 || n == 0) ? 1 : (n * (fact(n - 1, p)));
}
long long int nof(long long int n) {
  if (n == 1) {
    return 1;
  }
  long long int ans = 2;
  for (long long int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      if (i * i == n) {
        ans += 1;
      } else {
        ans += 2;
      }
    }
  }
  return ans;
}
long long int power(long long int num, long long int deg, long long int m) {
  if (!deg) return 1;
  if (deg % 2) {
    return (power(num, deg - 1, m) * num) % m;
  } else {
    long long int sqrt_res = power(num, deg / 2, m);
    return (sqrt_res * sqrt_res) % m;
  }
}
void seive(vector<long long int> &prm) {
  bool mark[102] = {false};
  long long int size = 102;
  mark[0] = true;
  mark[1] = true;
  for (long long int i = 2; i * i < size; i++) {
    if (mark[i] == false) {
      for (long long int j = i + i; j < size; j += i) {
        mark[j] = true;
      }
    }
  }
  for (long long int i = 0; i < 102; i++) {
    if (mark[i] == false) {
      prm.push_back(i);
    }
  }
}
bool stt(const pair<long long int, long long int> &a,
         const pair<long long int, long long int> &b) {
  return a.second < b.second;
}
long long int pp = 0;
void chk(vector<vector<long long int> > &cnt, long long int node,
         vector<long long int> &can, long long int tm, long long int mn) {
  if (can[node] == 0) {
    if (1) {
      if (cnt[node].size() != 2) {
        pp = 1;
        return;
      } else {
        return;
      }
    } else {
      return;
    }
  } else {
    return;
  }
  can[node] = 0;
  if (can[cnt[node][0]] == 1) {
    chk(cnt, cnt[node][0], can, tm + 1, mn);
    chk(cnt, cnt[node][1], can, tm + 1, mn);
  }
}
long long int calc(long long int n) {
  if (n / 10 == 0) {
    if (n == 0) {
      return 1;
    } else {
      return n;
    }
  }
  return max((n % 10 * calc(n / 10)), calc(n / 10 - 1) * 9);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int t = 1;
  while (t--) {
    long long int n;
    cin >> n;
    cout << calc(n);
  }
  return 0;
}

```