#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXLEN = 100;
const int MOD = 998244353;
void inc(int &a, int b) {
  if ((a += b) >= MOD) a -= MOD;
}
struct Ratio {
  int x, y;
  vector<pair<int, int>> pairs;
};
char s[MAXLEN + 1];
int slen;
vector<Ratio> ratios;
vector<int> p3;
vector<int> nums[10], dens[10];
int x, y;
int finstate;
int contrib[MAXLEN];
vector<int> mem[MAXLEN][10][10][2];
int go(int idx, int xcarry, int ycarry, int ok, int state) {
  if (idx < 0)
    return xcarry == 0 && ycarry == 0 && ok == 1 && state == finstate ? 1 : 0;
  assert(0 <= idx && idx < slen && 0 <= xcarry && xcarry < x && 0 <= ycarry &&
         ycarry < y && 0 <= ok && ok <= 1 && 0 <= state && state <= finstate);
  if (mem[idx][xcarry][ycarry][ok][state] != -1)
    return mem[idx][xcarry][ycarry][ok][state];
  int ret = 0;
  for (int b = (0); b <= (9); ++b) {
    int xval = xcarry + b * x, nxcarry = xval / 10, xdig = xval % 10;
    int yval = ycarry + b * y, nycarry = yval / 10, ydig = yval % 10,
        ylim = s[idx] - '0';
    int nok = ydig < ylim || ok == 1 && ydig == ylim ? 1 : 0;
    int nstate = state;
    for (int i = (0); i < (((int)(nums[xdig]).size())); ++i)
      if (nstate != finstate) {
        int z = nums[xdig][i], old = nstate / p3[z] % 3;
        if (old == 2)
          nstate = finstate;
        else if (old == 0)
          nstate += p3[z];
      }
    for (int i = (0); i < (((int)(dens[ydig]).size())); ++i)
      if (nstate != finstate) {
        int z = dens[ydig][i], old = nstate / p3[z] % 3;
        if (old == 1)
          nstate = finstate;
        else if (old == 0)
          nstate += 2 * p3[z];
      }
    int cur = go(idx - 1, nxcarry, nycarry, nok, nstate);
    inc(ret, cur);
  }
  return mem[idx][xcarry][ycarry][ok][state] = ret;
}
int calc(int i) {
  p3.clear();
  p3.push_back(1);
  for (int j = (0); j < (((int)(ratios[i].pairs).size())); ++j) {
    int nxt = p3.back() * 3;
    p3.push_back(nxt);
  }
  for (int j = (0); j < (10); ++j) nums[j].clear(), dens[j].clear();
  for (int j = (0); j < (((int)(ratios[i].pairs).size())); ++j)
    nums[ratios[i].pairs[j].first].push_back(j),
        dens[ratios[i].pairs[j].second].push_back(j);
  ::x = ratios[i].x, ::y = ratios[i].y,
  finstate = p3[((int)(ratios[i].pairs).size())];
  contrib[slen - 1] = 1;
  for (int i = slen - 2; i >= 0; --i) contrib[i] = 10 * contrib[i + 1] % y;
  int nstate = finstate + 1;
  for (int idx = (0); idx < (slen); ++idx)
    for (int xcarry = (0); xcarry < (x); ++xcarry)
      for (int ycarry = (0); ycarry < (y); ++ycarry)
        for (int ok = (0); ok < (2); ++ok)
          mem[idx][xcarry][ycarry][ok] = vector<int>(nstate, -1);
  int ret = go(slen - 1, 0, 0, 1, 0);
  for (int idx = (0); idx < (slen); ++idx)
    for (int xcarry = (0); xcarry < (x); ++xcarry)
      for (int ycarry = (0); ycarry < (y); ++ycarry)
        for (int ok = (0); ok < (2); ++ok)
          mem[idx][xcarry][ycarry][ok] = vector<int>();
  return ret;
}
int solve() {
  ratios.clear();
  for (int x = (1); x <= (9); ++x)
    for (int y = (x); y <= (9); ++y) {
      int idx = -1;
      for (int i = (0); i < (((int)(ratios).size())); ++i)
        if (x * ratios[i].y == ratios[i].x * y) {
          assert(idx == -1);
          idx = i;
        }
      if (idx != -1) {
        ratios[idx].pairs.push_back(make_pair(x, y));
        continue;
      }
      Ratio cur;
      cur.x = x, cur.y = y;
      cur.pairs.push_back(make_pair(x, y));
      ratios.push_back(cur);
    }
  int ret = 0;
  for (int i = (0); i < (((int)(ratios).size())); ++i) {
    int cur = calc(i);
    if (ratios[i].x != ratios[i].y) cur = (long long)cur * 2 % MOD;
    inc(ret, cur);
  }
  return ret;
}
void run() {
  scanf("%s", s);
  slen = strlen(s);
  printf("%d\n", solve());
}
bool contains(int x, int d) {
  while (x > 0) {
    if (x % 10 == d) return true;
    x /= 10;
  }
  return false;
}
int solvestupid(int n) {
  int ret = 0;
  for (int num = (1); num <= (n); ++num) {
    set<int> dens;
    for (int x = (1); x <= (9); ++x)
      if (contains(num, x))
        for (int y = (1); y <= (9); ++y)
          if ((num * y) % x == 0) {
            int den = (num * y) / x;
            if (den <= n && contains(den, y)) dens.insert(den);
          }
    ret += ((int)(dens).size());
  }
  return ret;
}
void stress() {
  for (int n = (1); n <= (1000); ++n) {
    sprintf(s, "%d", n);
    slen = strlen(s);
    int have = solve();
    int want = solvestupid(n);
    if (have == want) {
      printf(".");
      continue;
    }
    printf("%d: have=%d want=%d\n", n, have, want);
  }
}
int main() {
  run();
  return 0;
}

### Prompt

Your task is to create 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;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXLEN = 100;
const int MOD = 998244353;
void inc(int &a, int b) {
  if ((a += b) >= MOD) a -= MOD;
}
struct Ratio {
  int x, y;
  vector<pair<int, int>> pairs;
};
char s[MAXLEN + 1];
int slen;
vector<Ratio> ratios;
vector<int> p3;
vector<int> nums[10], dens[10];
int x, y;
int finstate;
int contrib[MAXLEN];
vector<int> mem[MAXLEN][10][10][2];
int go(int idx, int xcarry, int ycarry, int ok, int state) {
  if (idx < 0)
    return xcarry == 0 && ycarry == 0 && ok == 1 && state == finstate ? 1 : 0;
  assert(0 <= idx && idx < slen && 0 <= xcarry && xcarry < x && 0 <= ycarry &&
         ycarry < y && 0 <= ok && ok <= 1 && 0 <= state && state <= finstate);
  if (mem[idx][xcarry][ycarry][ok][state] != -1)
    return mem[idx][xcarry][ycarry][ok][state];
  int ret = 0;
  for (int b = (0); b <= (9); ++b) {
    int xval = xcarry + b * x, nxcarry = xval / 10, xdig = xval % 10;
    int yval = ycarry + b * y, nycarry = yval / 10, ydig = yval % 10,
        ylim = s[idx] - '0';
    int nok = ydig < ylim || ok == 1 && ydig == ylim ? 1 : 0;
    int nstate = state;
    for (int i = (0); i < (((int)(nums[xdig]).size())); ++i)
      if (nstate != finstate) {
        int z = nums[xdig][i], old = nstate / p3[z] % 3;
        if (old == 2)
          nstate = finstate;
        else if (old == 0)
          nstate += p3[z];
      }
    for (int i = (0); i < (((int)(dens[ydig]).size())); ++i)
      if (nstate != finstate) {
        int z = dens[ydig][i], old = nstate / p3[z] % 3;
        if (old == 1)
          nstate = finstate;
        else if (old == 0)
          nstate += 2 * p3[z];
      }
    int cur = go(idx - 1, nxcarry, nycarry, nok, nstate);
    inc(ret, cur);
  }
  return mem[idx][xcarry][ycarry][ok][state] = ret;
}
int calc(int i) {
  p3.clear();
  p3.push_back(1);
  for (int j = (0); j < (((int)(ratios[i].pairs).size())); ++j) {
    int nxt = p3.back() * 3;
    p3.push_back(nxt);
  }
  for (int j = (0); j < (10); ++j) nums[j].clear(), dens[j].clear();
  for (int j = (0); j < (((int)(ratios[i].pairs).size())); ++j)
    nums[ratios[i].pairs[j].first].push_back(j),
        dens[ratios[i].pairs[j].second].push_back(j);
  ::x = ratios[i].x, ::y = ratios[i].y,
  finstate = p3[((int)(ratios[i].pairs).size())];
  contrib[slen - 1] = 1;
  for (int i = slen - 2; i >= 0; --i) contrib[i] = 10 * contrib[i + 1] % y;
  int nstate = finstate + 1;
  for (int idx = (0); idx < (slen); ++idx)
    for (int xcarry = (0); xcarry < (x); ++xcarry)
      for (int ycarry = (0); ycarry < (y); ++ycarry)
        for (int ok = (0); ok < (2); ++ok)
          mem[idx][xcarry][ycarry][ok] = vector<int>(nstate, -1);
  int ret = go(slen - 1, 0, 0, 1, 0);
  for (int idx = (0); idx < (slen); ++idx)
    for (int xcarry = (0); xcarry < (x); ++xcarry)
      for (int ycarry = (0); ycarry < (y); ++ycarry)
        for (int ok = (0); ok < (2); ++ok)
          mem[idx][xcarry][ycarry][ok] = vector<int>();
  return ret;
}
int solve() {
  ratios.clear();
  for (int x = (1); x <= (9); ++x)
    for (int y = (x); y <= (9); ++y) {
      int idx = -1;
      for (int i = (0); i < (((int)(ratios).size())); ++i)
        if (x * ratios[i].y == ratios[i].x * y) {
          assert(idx == -1);
          idx = i;
        }
      if (idx != -1) {
        ratios[idx].pairs.push_back(make_pair(x, y));
        continue;
      }
      Ratio cur;
      cur.x = x, cur.y = y;
      cur.pairs.push_back(make_pair(x, y));
      ratios.push_back(cur);
    }
  int ret = 0;
  for (int i = (0); i < (((int)(ratios).size())); ++i) {
    int cur = calc(i);
    if (ratios[i].x != ratios[i].y) cur = (long long)cur * 2 % MOD;
    inc(ret, cur);
  }
  return ret;
}
void run() {
  scanf("%s", s);
  slen = strlen(s);
  printf("%d\n", solve());
}
bool contains(int x, int d) {
  while (x > 0) {
    if (x % 10 == d) return true;
    x /= 10;
  }
  return false;
}
int solvestupid(int n) {
  int ret = 0;
  for (int num = (1); num <= (n); ++num) {
    set<int> dens;
    for (int x = (1); x <= (9); ++x)
      if (contains(num, x))
        for (int y = (1); y <= (9); ++y)
          if ((num * y) % x == 0) {
            int den = (num * y) / x;
            if (den <= n && contains(den, y)) dens.insert(den);
          }
    ret += ((int)(dens).size());
  }
  return ret;
}
void stress() {
  for (int n = (1); n <= (1000); ++n) {
    sprintf(s, "%d", n);
    slen = strlen(s);
    int have = solve();
    int want = solvestupid(n);
    if (have == want) {
      printf(".");
      continue;
    }
    printf("%d: have=%d want=%d\n", n, have, want);
  }
}
int main() {
  run();
  return 0;
}

```