#include <bits/stdc++.h>
using namespace std;
const long long int modulo = 998244353;
void add(int &a, long long int b) { a = (a + b) % modulo; }
int n;
int v[105];
int d2c1[10], d2c2[10];
int d1, d2;
int memcompute[105][10][10][3][3][8][8][2][2];
int comcompute[105][10][10][3][3][8][8][2][2];
int getnextg(int pos, int D, int g) {
  if (D > v[pos] or (D == v[pos] and g == 2)) return 2;
  if (D == v[pos] and g == 1) return 1;
  return 0;
}
int compute(int pos, int carry1, int carry2, int g1, int g2, int c1, int c2,
            int s1, int s2) {
  if (pos == -1) return 0;
  int &mem = memcompute[pos][carry1][carry2][g1][g2][c1][c2][s1][s2];
  int &com = comcompute[pos][carry1][carry2][g1][g2][c1][c2][s1][s2];
  if (com) {
    return mem;
  }
  com = 1;
  for (int D1 = 0; D1 < 10; D1++) {
    for (int D2 = 0; D2 < 10; D2++) {
      int v1 = carry1 + D1 * d1;
      int v2 = carry2 + D2 * d2;
      if (v1 % 10 != v2 % 10) continue;
      int nextc1 = c1 | d2c1[D1];
      int nextc2 = c2 | d2c2[D2];
      if (nextc1 & nextc2) continue;
      int nexts1 = s1 or D2 == d1;
      int nexts2 = s2 or D1 == d2;
      int nextcarry1 = v1 / 10;
      int nextcarry2 = v2 / 10;
      int nextg1 = getnextg(pos, D1, g1);
      int nextg2 = getnextg(pos, D2, g2);
      if (nexts1 and nexts2 and (nextcarry1 == nextcarry2) and
          (D1 > 0 or D2 > 0) and (pos > 0 or (nextg1 <= 1 and nextg2 <= 1)))
        add(mem, 1);
      long long int res = compute(pos - 1, nextcarry1, nextcarry2, nextg1,
                                  nextg2, nextc1, nextc2, nexts1, nexts2);
      add(mem, res);
    }
  }
  return mem;
}
int sol;
void compute() {
  for (int i = 0; i < 10; i++) d2c1[i] = d2c2[i] = 0;
  int amount = 0;
  for (int D1 = d1 - 1; D1 >= 1; D1--) {
    if (D1 * d2 % d1 == 0 and D1 * d2 / d1 < 10) {
      d2c1[D1 * d2 / d1] = 1 << amount;
      d2c2[D1] = 1 << amount;
      amount++;
    }
  }
  for (int pos = 0; pos < n; pos++)
    for (int carry1 = 0; carry1 < 10; carry1++)
      for (int carry2 = 0; carry2 < 10; carry2++)
        for (int g1 = 0; g1 < 3; g1++)
          for (int g2 = 0; g2 < 3; g2++)
            for (int c1 = 0; c1 < 1 << amount; c1++)
              for (int c2 = 0; c2 < 1 << amount; c2++)
                for (int s1 = 0; s1 < 2; s1++)
                  for (int s2 = 0; s2 < 2; s2++)
                    memcompute[pos][carry1][carry2][g1][g2][c1][c2][s1][s2] =
                        comcompute[pos][carry1][carry2][g1][g2][c1][c2][s1]
                                  [s2] = 0;
  long long int res = compute(n - 1, 0, 0, 1, 1, 0, 0, 0, 0);
  add(sol, 2 * res);
}
int memcomputeid[105][3][2];
int comcomputeid[105][3][2];
int computeid(int pos, int g, int s) {
  if (pos < 0) return 0;
  int &mem = memcomputeid[pos][g][s];
  int &com = comcomputeid[pos][g][s];
  if (com) return mem;
  com = 1;
  for (int D = 0; D < 10; D++) {
    if (0 < D and D < d1) continue;
    int nextg = getnextg(pos, D, g);
    int nexts = s or D == d1;
    if (nexts and D > 0 and (pos > 0 or nextg <= 1)) {
      add(mem, 1);
    }
    add(mem, computeid(pos - 1, nextg, nexts));
  }
  return mem;
}
void computeid() {
  for (int pos = 0; pos < n; pos++)
    for (int g = 0; g < 3; g++)
      for (int s = 0; s < 2; s++)
        memcomputeid[pos][g][s] = comcomputeid[pos][g][s] = 0;
  long long int res = computeid(n - 1, 1, 0);
  add(sol, res);
}
int main() {
  string s;
  cin >> s;
  n = int(s.size());
  for (int i = 0; i < n; i++) v[i] = s[i] - '0';
  for (d1 = 1; d1 < 10; d1++) {
    for (d2 = d1; d2 < 10; d2++) {
      if (d1 == d2)
        computeid();
      else
        compute();
    }
  }
  cout << sol << endl;
}

### Prompt

Develop a solution in cpp to the problem described below:

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 long long int modulo = 998244353;
void add(int &a, long long int b) { a = (a + b) % modulo; }
int n;
int v[105];
int d2c1[10], d2c2[10];
int d1, d2;
int memcompute[105][10][10][3][3][8][8][2][2];
int comcompute[105][10][10][3][3][8][8][2][2];
int getnextg(int pos, int D, int g) {
  if (D > v[pos] or (D == v[pos] and g == 2)) return 2;
  if (D == v[pos] and g == 1) return 1;
  return 0;
}
int compute(int pos, int carry1, int carry2, int g1, int g2, int c1, int c2,
            int s1, int s2) {
  if (pos == -1) return 0;
  int &mem = memcompute[pos][carry1][carry2][g1][g2][c1][c2][s1][s2];
  int &com = comcompute[pos][carry1][carry2][g1][g2][c1][c2][s1][s2];
  if (com) {
    return mem;
  }
  com = 1;
  for (int D1 = 0; D1 < 10; D1++) {
    for (int D2 = 0; D2 < 10; D2++) {
      int v1 = carry1 + D1 * d1;
      int v2 = carry2 + D2 * d2;
      if (v1 % 10 != v2 % 10) continue;
      int nextc1 = c1 | d2c1[D1];
      int nextc2 = c2 | d2c2[D2];
      if (nextc1 & nextc2) continue;
      int nexts1 = s1 or D2 == d1;
      int nexts2 = s2 or D1 == d2;
      int nextcarry1 = v1 / 10;
      int nextcarry2 = v2 / 10;
      int nextg1 = getnextg(pos, D1, g1);
      int nextg2 = getnextg(pos, D2, g2);
      if (nexts1 and nexts2 and (nextcarry1 == nextcarry2) and
          (D1 > 0 or D2 > 0) and (pos > 0 or (nextg1 <= 1 and nextg2 <= 1)))
        add(mem, 1);
      long long int res = compute(pos - 1, nextcarry1, nextcarry2, nextg1,
                                  nextg2, nextc1, nextc2, nexts1, nexts2);
      add(mem, res);
    }
  }
  return mem;
}
int sol;
void compute() {
  for (int i = 0; i < 10; i++) d2c1[i] = d2c2[i] = 0;
  int amount = 0;
  for (int D1 = d1 - 1; D1 >= 1; D1--) {
    if (D1 * d2 % d1 == 0 and D1 * d2 / d1 < 10) {
      d2c1[D1 * d2 / d1] = 1 << amount;
      d2c2[D1] = 1 << amount;
      amount++;
    }
  }
  for (int pos = 0; pos < n; pos++)
    for (int carry1 = 0; carry1 < 10; carry1++)
      for (int carry2 = 0; carry2 < 10; carry2++)
        for (int g1 = 0; g1 < 3; g1++)
          for (int g2 = 0; g2 < 3; g2++)
            for (int c1 = 0; c1 < 1 << amount; c1++)
              for (int c2 = 0; c2 < 1 << amount; c2++)
                for (int s1 = 0; s1 < 2; s1++)
                  for (int s2 = 0; s2 < 2; s2++)
                    memcompute[pos][carry1][carry2][g1][g2][c1][c2][s1][s2] =
                        comcompute[pos][carry1][carry2][g1][g2][c1][c2][s1]
                                  [s2] = 0;
  long long int res = compute(n - 1, 0, 0, 1, 1, 0, 0, 0, 0);
  add(sol, 2 * res);
}
int memcomputeid[105][3][2];
int comcomputeid[105][3][2];
int computeid(int pos, int g, int s) {
  if (pos < 0) return 0;
  int &mem = memcomputeid[pos][g][s];
  int &com = comcomputeid[pos][g][s];
  if (com) return mem;
  com = 1;
  for (int D = 0; D < 10; D++) {
    if (0 < D and D < d1) continue;
    int nextg = getnextg(pos, D, g);
    int nexts = s or D == d1;
    if (nexts and D > 0 and (pos > 0 or nextg <= 1)) {
      add(mem, 1);
    }
    add(mem, computeid(pos - 1, nextg, nexts));
  }
  return mem;
}
void computeid() {
  for (int pos = 0; pos < n; pos++)
    for (int g = 0; g < 3; g++)
      for (int s = 0; s < 2; s++)
        memcomputeid[pos][g][s] = comcomputeid[pos][g][s] = 0;
  long long int res = computeid(n - 1, 1, 0);
  add(sol, res);
}
int main() {
  string s;
  cin >> s;
  n = int(s.size());
  for (int i = 0; i < n; i++) v[i] = s[i] - '0';
  for (d1 = 1; d1 < 10; d1++) {
    for (d2 = d1; d2 < 10; d2++) {
      if (d1 == d2)
        computeid();
      else
        compute();
    }
  }
  cout << sol << endl;
}

```