#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fll;
const long long M = 998244353;
const long long maxn = 1e6 + 7;
const double pi = acos(-1.0);
const double eps = 1e-10;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline void pr2(T x, int k = 64) {
  long long i;
  for (i = 0; i < k; i++) fprintf(stderr, "%d", (x >> i) & 1);
  putchar(' ');
}
template <typename T>
inline void add_(T &A, int B, long long MOD = M) {
  A += B;
  (A >= MOD) && (A -= MOD);
}
template <typename T>
inline void mul_(T &A, long long B, long long MOD = M) {
  A = (A * B) % MOD;
}
template <typename T>
inline void mod_(T &A, long long MOD = M) {
  A %= MOD;
  A += MOD;
  A %= MOD;
}
template <typename T>
inline void max_(T &A, T B) {
  (A < B) && (A = B);
}
template <typename T>
inline void min_(T &A, T B) {
  (A > B) && (A = B);
}
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
inline long long powMM(long long a, long long b, long long mod = M) {
  long long ret = 1;
  for (; b; b >>= 1ll, a = a * a % mod)
    if (b & 1) ret = ret * a % mod;
  return ret;
}
int startTime;
void startTimer() { startTime = clock(); }
void printTimer() {
  fprintf(stderr, "/--- Time: %ld milliseconds ---/\n", clock() - startTime);
}
int f[107][10][10][1 << 10][3];
char s[maxn];
vector<pair<int, int> > now;
int n;
int X, Y;
int query(int pos, int more_x, int more_y, int mask, int more) {
  if (pos == n) {
    if (more_x || more_y || !more) return 0;
    bool okay = 0;
    int i;
    for (i = 0; i < (int)now.size(); i++)
      if (((mask >> (i * 2)) & 3) == 3) okay = 1;
    return okay;
  }
  if (f[pos][more_x][more_y][mask][more] != -1)
    return f[pos][more_x][more_y][mask][more];
  int ret = 0, k, i;
  for (k = 0; k < 10; k++) {
    int nowx = X * k + more_x, nowy = Y * k + more_y;
    int ax = nowx % 10, ay = nowy % 10, nxtmask = mask, nxtmore = more;
    for (i = 0; i < (int)now.size(); i++) {
      if (ax == now[i].first) nxtmask |= 1 << (i * 2);
      if (ay == now[i].second) nxtmask |= 1 << (i * 2 + 1);
    }
    if (ay > s[pos] - '0') nxtmore = 0;
    if (ay < s[pos] - '0') nxtmore = 2;
    add_(ret, query(pos + 1, nowx / 10, nowy / 10, nxtmask, nxtmore));
  }
  return f[pos][more_x][more_y][mask][more] = ret;
}
int main() {
  scanf("%s", s);
  n = strlen(s);
  reverse(s, s + n);
  int i, j, k;
  int ans = 0;
  for (i = 1; i <= 9; i++)
    for (j = i; j <= 9; j++)
      if (gcd(i, j) == 1) {
        X = i;
        Y = j;
        if (i == 1 && j == 1) {
          int base = 1;
          ans = 0;
          for (k = 0; k < n; k++)
            add_(ans, (long long)base * (s[k] - '0') % M), mul_(base, 10);
        } else {
          now.clear();
          for (k = 1; k <= 10; k++)
            if (k * i <= 9 && k * j <= 9)
              now.push_back(make_pair(i * k, j * k));
          int _l, _i, _j, _sta, _m;
          for (_l = 0; _l < n; _l++)
            for (_i = 0; _i < 10; _i++)
              for (_j = 0; _j < 10; _j++)
                for (_sta = 0; _sta < (1 << ((int)now.size() * 2)); _sta++)
                  for (_m = 0; _m < 3; _m++) {
                    f[_l][_i][_j][_sta][_m] = -1;
                  }
          memset(f, 0xff, sizeof(f));
          int base = query(0, 0, 0, 0, 1);
          add_(ans, base);
          if (i != j) add_(ans, base);
        }
      }
  printf("%d\n", ans);
}

### Prompt

Generate a Cpp solution to the following problem:

Let's call a fraction x/y good if there exists at least one another fraction (x')/(y') such that x/y = (x')/(y'), 1 ≤ x', y' ≤ 9, the digit denoting x' is contained in the decimal representation of x, and the digit denoting y' is contained in the decimal representation of y. For example, 26/13 is a good fraction, because 26/13 = 2/1.

You are given an integer number n. Please calculate the number of good fractions x/y such that 1 ≤ x ≤ n and 1 ≤ y ≤ n. The answer may be really large, so print it modulo 998244353.

Input

The only line of the input contains one integer n (1 ≤ n < 10^{100}).

Output

Print the number of good fractions x/y such that 1 ≤ x ≤ n and 1 ≤ y ≤ n. The answer may be really large, so print it modulo 998244353.

Examples

Input


42


Output


150


Input


3141592653589793238462643383279


Output


459925407

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fll;
const long long M = 998244353;
const long long maxn = 1e6 + 7;
const double pi = acos(-1.0);
const double eps = 1e-10;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline void pr2(T x, int k = 64) {
  long long i;
  for (i = 0; i < k; i++) fprintf(stderr, "%d", (x >> i) & 1);
  putchar(' ');
}
template <typename T>
inline void add_(T &A, int B, long long MOD = M) {
  A += B;
  (A >= MOD) && (A -= MOD);
}
template <typename T>
inline void mul_(T &A, long long B, long long MOD = M) {
  A = (A * B) % MOD;
}
template <typename T>
inline void mod_(T &A, long long MOD = M) {
  A %= MOD;
  A += MOD;
  A %= MOD;
}
template <typename T>
inline void max_(T &A, T B) {
  (A < B) && (A = B);
}
template <typename T>
inline void min_(T &A, T B) {
  (A > B) && (A = B);
}
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
inline long long powMM(long long a, long long b, long long mod = M) {
  long long ret = 1;
  for (; b; b >>= 1ll, a = a * a % mod)
    if (b & 1) ret = ret * a % mod;
  return ret;
}
int startTime;
void startTimer() { startTime = clock(); }
void printTimer() {
  fprintf(stderr, "/--- Time: %ld milliseconds ---/\n", clock() - startTime);
}
int f[107][10][10][1 << 10][3];
char s[maxn];
vector<pair<int, int> > now;
int n;
int X, Y;
int query(int pos, int more_x, int more_y, int mask, int more) {
  if (pos == n) {
    if (more_x || more_y || !more) return 0;
    bool okay = 0;
    int i;
    for (i = 0; i < (int)now.size(); i++)
      if (((mask >> (i * 2)) & 3) == 3) okay = 1;
    return okay;
  }
  if (f[pos][more_x][more_y][mask][more] != -1)
    return f[pos][more_x][more_y][mask][more];
  int ret = 0, k, i;
  for (k = 0; k < 10; k++) {
    int nowx = X * k + more_x, nowy = Y * k + more_y;
    int ax = nowx % 10, ay = nowy % 10, nxtmask = mask, nxtmore = more;
    for (i = 0; i < (int)now.size(); i++) {
      if (ax == now[i].first) nxtmask |= 1 << (i * 2);
      if (ay == now[i].second) nxtmask |= 1 << (i * 2 + 1);
    }
    if (ay > s[pos] - '0') nxtmore = 0;
    if (ay < s[pos] - '0') nxtmore = 2;
    add_(ret, query(pos + 1, nowx / 10, nowy / 10, nxtmask, nxtmore));
  }
  return f[pos][more_x][more_y][mask][more] = ret;
}
int main() {
  scanf("%s", s);
  n = strlen(s);
  reverse(s, s + n);
  int i, j, k;
  int ans = 0;
  for (i = 1; i <= 9; i++)
    for (j = i; j <= 9; j++)
      if (gcd(i, j) == 1) {
        X = i;
        Y = j;
        if (i == 1 && j == 1) {
          int base = 1;
          ans = 0;
          for (k = 0; k < n; k++)
            add_(ans, (long long)base * (s[k] - '0') % M), mul_(base, 10);
        } else {
          now.clear();
          for (k = 1; k <= 10; k++)
            if (k * i <= 9 && k * j <= 9)
              now.push_back(make_pair(i * k, j * k));
          int _l, _i, _j, _sta, _m;
          for (_l = 0; _l < n; _l++)
            for (_i = 0; _i < 10; _i++)
              for (_j = 0; _j < 10; _j++)
                for (_sta = 0; _sta < (1 << ((int)now.size() * 2)); _sta++)
                  for (_m = 0; _m < 3; _m++) {
                    f[_l][_i][_j][_sta][_m] = -1;
                  }
          memset(f, 0xff, sizeof(f));
          int base = query(0, 0, 0, 0, 1);
          add_(ans, base);
          if (i != j) add_(ans, base);
        }
      }
  printf("%d\n", ans);
}

```