#include <bits/stdc++.h>
using namespace std;
int k;
long long mod = 998244353;
long long memo[25][4][5000];
long long memo2[25][4][5000];
int cnt[5000];
string A, B;
long long bigmod(long long b, long long p, long long m) {
  if (p == 0) return 1;
  if (p % 2 == 0) {
    long long temp = bigmod(b, p / 2, m);
    return (temp * temp) % m;
  }
  return (bigmod(b, p - 1, m) * (b % m)) % m;
}
long long solve(int i, int ok, int mask) {
  if (i == 18) {
    if (mask == 0) {
      memo[i][ok][mask] = 0;
      return 0;
    }
    memo[i][ok][mask] = (cnt[mask] <= k);
    return cnt[mask] <= k;
  }
  long long &ret = memo[i][ok][mask];
  if (ret != -1) return ret;
  ret = 0;
  if (ok == 0) {
    int st = A[i] - '0';
    int En = B[i] - '0';
    for (int j = 0; j < 10; j++) {
      if (j >= st && j <= En) {
        if (st == En) {
          if (j == 0 && mask == 0)
            ret += solve(i + 1, 0, mask);
          else
            ret += solve(i + 1, 0, mask | (1 << j));
        } else {
          if (j == En) {
            ret += solve(i + 1, 1, mask | (1 << j));
          } else if (j == st) {
            if (j == 0 && mask == 0)
              ret += solve(i + 1, 2, mask);
            else {
              ret += solve(i + 1, 2, mask | (1 << j));
            }
          } else {
            ret += solve(i + 1, 3, mask | (1 << j));
          }
        }
      }
    }
  } else if (ok == 1) {
    int En = B[i] - '0';
    for (int j = 0; j < 10; j++) {
      if (j <= En) {
        if (j == 0) {
          int mask2 = 0;
          if (mask != 0) mask2 = mask | (1 << j);
          if (j == En) {
            ret += solve(i + 1, 1, mask2);
          } else {
            ret += solve(i + 1, 3, mask2);
          }
        } else {
          if (j == En) {
            ret += solve(i + 1, 1, mask | (1 << j));
          } else {
            ret += solve(i + 1, 3, mask | (1 << j));
          }
        }
      }
    }
  } else if (ok == 2) {
    int st = A[i] - '0';
    for (int j = 0; j < 10; j++) {
      if (j >= st) {
        int mask2 = mask | (1 << j);
        if (mask == 0 && j == 0) {
          mask2 = 0;
        }
        if (j == st) {
          ret += solve(i + 1, 2, mask2);
        } else {
          ret += solve(i + 1, 3, mask2);
        }
      }
    }
  } else {
    for (int j = 0; j < 10; j++) {
      int mask2 = mask | (1 << j);
      if (j == 0 && mask == 0) mask2 = 0;
      ret += solve(i + 1, 3, mask2);
    }
  }
  return ret;
}
long long solve2(int i, int ok, int mask) {
  if (i == 18) {
    return 0;
  }
  long long &ret = memo2[i][ok][mask];
  if (ret != -1) return ret;
  ret = 0;
  if (ok == 0) {
    int st = A[i] - '0';
    int En = B[i] - '0';
    for (int j = 0; j < 10; j++) {
      if (j >= st && j <= En) {
        if (st == En) {
          if (j == 0 && mask == 0) {
            long long R = memo[i + 1][0][mask];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 0, mask);
            ret %= mod;
          } else {
            long long R = memo[i + 1][0][mask | (1 << j)];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 0, mask | (1 << j));
            ret %= mod;
          }
        } else {
          if (j == En) {
            long long R = memo[i + 1][1][mask | (1 << j)];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 1, mask | (1 << j));
            ret %= mod;
          } else if (j == st) {
            if (j == 0 && mask == 0) {
              long long R = memo[i + 1][2][mask];
              R %= mod;
              long long F = R * bigmod(10, 17 - i, mod);
              F %= mod;
              F = F * j;
              ret += F;
              ret %= mod;
              ret += solve2(i + 1, 2, mask);
              ret %= mod;
            } else {
              long long R = memo[i + 1][2][mask | (1 << j)];
              R %= mod;
              long long F = R * bigmod(10, 17 - i, mod);
              F %= mod;
              F = F * j;
              ret += F;
              ret %= mod;
              ret += solve2(i + 1, 2, mask | (1 << j));
              ret %= mod;
            }
          } else {
            long long R = memo[i + 1][3][mask | (1 << j)];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 3, mask | (1 << j));
            ret %= mod;
          }
        }
        ret %= mod;
      }
    }
  } else if (ok == 1) {
    int En = B[i] - '0';
    for (int j = 0; j < 10; j++) {
      if (j <= En) {
        if (j == 0) {
          int mask2 = 0;
          if (mask != 0) mask2 = mask | (1 << j);
          if (j == En) {
            long long R = memo[i + 1][1][mask2];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 1, mask2);
            ret %= mod;
          } else {
            long long R = memo[i + 1][3][mask2];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 3, mask2);
            ret %= mod;
          }
        } else {
          if (j == En) {
            long long R = memo[i + 1][1][mask | (1 << j)];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 1, mask | (1 << j));
            ret %= mod;
          } else {
            long long R = memo[i + 1][3][mask | (1 << j)];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 3, mask | (1 << j));
            ret %= mod;
          }
        }
        ret %= mod;
      }
    }
  } else if (ok == 2) {
    int st = A[i] - '0';
    for (int j = 0; j < 10; j++) {
      if (j >= st) {
        int mask2 = mask | (1 << j);
        if (mask == 0 && j == 0) {
          mask2 = 0;
        }
        if (j == st) {
          long long R = memo[i + 1][2][mask2];
          R %= mod;
          long long F = R * bigmod(10, 17 - i, mod);
          F %= mod;
          F = F * j;
          ret += F;
          ret %= mod;
          ret += solve2(i + 1, 2, mask2);
          ret %= mod;
        } else {
          long long R = memo[i + 1][3][mask2];
          R %= mod;
          long long F = R * bigmod(10, 17 - i, mod);
          F %= mod;
          F = F * j;
          ret += F;
          ret %= mod;
          ret += solve2(i + 1, 3, mask2);
          ret %= mod;
        }
        ret %= mod;
      }
    }
  } else {
    for (int j = 0; j < 10; j++) {
      int mask2 = mask | (1 << j);
      if (j == 0 && mask == 0) mask2 = 0;
      long long R = memo[i + 1][3][mask2];
      R %= mod;
      long long F = R * bigmod(10, 17 - i, mod);
      F %= mod;
      F = F * j;
      ret += F;
      ret %= mod;
      ret += solve2(i + 1, 3, mask2);
      ret %= mod;
    }
  }
  ret %= mod;
  return ret;
}
int main() {
  memset(memo, -1, sizeof(memo));
  memset(memo2, -1, sizeof(memo2));
  for (int i = 0; i < 5000; i++) {
    int x = i;
    for (int j = 0; j < 10; j++) {
      if (x & (1 << j)) cnt[i]++;
    }
  }
  cin >> A >> B >> k;
  while (A.length() < 18) {
    A = '0' + A;
  }
  while (B.length() < 18) {
    B = '0' + B;
  }
  solve(0, 0, 0);
  cout << solve2(0, 0, 0) % mod;
}

### Prompt

Please formulate a cpp solution to the following problem:

You are given two integers l and r (l ≤ r). Your task is to calculate the sum of numbers from l to r (including l and r) such that each number contains at most k different digits, and print this sum modulo 998244353.

For example, if k = 1 then you have to calculate all numbers from l to r such that each number is formed using only one digit. For l = 10, r = 50 the answer is 11 + 22 + 33 + 44 = 110.

Input

The only line of the input contains three integers l, r and k (1 ≤ l ≤ r < 10^{18}, 1 ≤ k ≤ 10) — the borders of the segment and the maximum number of different digits.

Output

Print one integer — the sum of numbers from l to r such that each number contains at most k different digits, modulo 998244353.

Examples

Input

10 50 2


Output

1230


Input

1 2345 10


Output

2750685


Input

101 154 2


Output

2189

Note

For the first example the answer is just the sum of numbers from l to r which equals to (50 ⋅ 51)/(2) - (9 ⋅ 10)/(2) = 1230. This example also explained in the problem statement but for k = 1.

For the second example the answer is just the sum of numbers from l to r which equals to (2345 ⋅ 2346)/(2) = 2750685.

For the third example the answer is 101 + 110 + 111 + 112 + 113 + 114 + 115 + 116 + 117 + 118 + 119 + 121 + 122 + 131 + 133 + 141 + 144 + 151 = 2189.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int k;
long long mod = 998244353;
long long memo[25][4][5000];
long long memo2[25][4][5000];
int cnt[5000];
string A, B;
long long bigmod(long long b, long long p, long long m) {
  if (p == 0) return 1;
  if (p % 2 == 0) {
    long long temp = bigmod(b, p / 2, m);
    return (temp * temp) % m;
  }
  return (bigmod(b, p - 1, m) * (b % m)) % m;
}
long long solve(int i, int ok, int mask) {
  if (i == 18) {
    if (mask == 0) {
      memo[i][ok][mask] = 0;
      return 0;
    }
    memo[i][ok][mask] = (cnt[mask] <= k);
    return cnt[mask] <= k;
  }
  long long &ret = memo[i][ok][mask];
  if (ret != -1) return ret;
  ret = 0;
  if (ok == 0) {
    int st = A[i] - '0';
    int En = B[i] - '0';
    for (int j = 0; j < 10; j++) {
      if (j >= st && j <= En) {
        if (st == En) {
          if (j == 0 && mask == 0)
            ret += solve(i + 1, 0, mask);
          else
            ret += solve(i + 1, 0, mask | (1 << j));
        } else {
          if (j == En) {
            ret += solve(i + 1, 1, mask | (1 << j));
          } else if (j == st) {
            if (j == 0 && mask == 0)
              ret += solve(i + 1, 2, mask);
            else {
              ret += solve(i + 1, 2, mask | (1 << j));
            }
          } else {
            ret += solve(i + 1, 3, mask | (1 << j));
          }
        }
      }
    }
  } else if (ok == 1) {
    int En = B[i] - '0';
    for (int j = 0; j < 10; j++) {
      if (j <= En) {
        if (j == 0) {
          int mask2 = 0;
          if (mask != 0) mask2 = mask | (1 << j);
          if (j == En) {
            ret += solve(i + 1, 1, mask2);
          } else {
            ret += solve(i + 1, 3, mask2);
          }
        } else {
          if (j == En) {
            ret += solve(i + 1, 1, mask | (1 << j));
          } else {
            ret += solve(i + 1, 3, mask | (1 << j));
          }
        }
      }
    }
  } else if (ok == 2) {
    int st = A[i] - '0';
    for (int j = 0; j < 10; j++) {
      if (j >= st) {
        int mask2 = mask | (1 << j);
        if (mask == 0 && j == 0) {
          mask2 = 0;
        }
        if (j == st) {
          ret += solve(i + 1, 2, mask2);
        } else {
          ret += solve(i + 1, 3, mask2);
        }
      }
    }
  } else {
    for (int j = 0; j < 10; j++) {
      int mask2 = mask | (1 << j);
      if (j == 0 && mask == 0) mask2 = 0;
      ret += solve(i + 1, 3, mask2);
    }
  }
  return ret;
}
long long solve2(int i, int ok, int mask) {
  if (i == 18) {
    return 0;
  }
  long long &ret = memo2[i][ok][mask];
  if (ret != -1) return ret;
  ret = 0;
  if (ok == 0) {
    int st = A[i] - '0';
    int En = B[i] - '0';
    for (int j = 0; j < 10; j++) {
      if (j >= st && j <= En) {
        if (st == En) {
          if (j == 0 && mask == 0) {
            long long R = memo[i + 1][0][mask];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 0, mask);
            ret %= mod;
          } else {
            long long R = memo[i + 1][0][mask | (1 << j)];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 0, mask | (1 << j));
            ret %= mod;
          }
        } else {
          if (j == En) {
            long long R = memo[i + 1][1][mask | (1 << j)];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 1, mask | (1 << j));
            ret %= mod;
          } else if (j == st) {
            if (j == 0 && mask == 0) {
              long long R = memo[i + 1][2][mask];
              R %= mod;
              long long F = R * bigmod(10, 17 - i, mod);
              F %= mod;
              F = F * j;
              ret += F;
              ret %= mod;
              ret += solve2(i + 1, 2, mask);
              ret %= mod;
            } else {
              long long R = memo[i + 1][2][mask | (1 << j)];
              R %= mod;
              long long F = R * bigmod(10, 17 - i, mod);
              F %= mod;
              F = F * j;
              ret += F;
              ret %= mod;
              ret += solve2(i + 1, 2, mask | (1 << j));
              ret %= mod;
            }
          } else {
            long long R = memo[i + 1][3][mask | (1 << j)];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 3, mask | (1 << j));
            ret %= mod;
          }
        }
        ret %= mod;
      }
    }
  } else if (ok == 1) {
    int En = B[i] - '0';
    for (int j = 0; j < 10; j++) {
      if (j <= En) {
        if (j == 0) {
          int mask2 = 0;
          if (mask != 0) mask2 = mask | (1 << j);
          if (j == En) {
            long long R = memo[i + 1][1][mask2];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 1, mask2);
            ret %= mod;
          } else {
            long long R = memo[i + 1][3][mask2];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 3, mask2);
            ret %= mod;
          }
        } else {
          if (j == En) {
            long long R = memo[i + 1][1][mask | (1 << j)];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 1, mask | (1 << j));
            ret %= mod;
          } else {
            long long R = memo[i + 1][3][mask | (1 << j)];
            R %= mod;
            long long F = R * bigmod(10, 17 - i, mod);
            F %= mod;
            F = F * j;
            ret += F;
            ret %= mod;
            ret += solve2(i + 1, 3, mask | (1 << j));
            ret %= mod;
          }
        }
        ret %= mod;
      }
    }
  } else if (ok == 2) {
    int st = A[i] - '0';
    for (int j = 0; j < 10; j++) {
      if (j >= st) {
        int mask2 = mask | (1 << j);
        if (mask == 0 && j == 0) {
          mask2 = 0;
        }
        if (j == st) {
          long long R = memo[i + 1][2][mask2];
          R %= mod;
          long long F = R * bigmod(10, 17 - i, mod);
          F %= mod;
          F = F * j;
          ret += F;
          ret %= mod;
          ret += solve2(i + 1, 2, mask2);
          ret %= mod;
        } else {
          long long R = memo[i + 1][3][mask2];
          R %= mod;
          long long F = R * bigmod(10, 17 - i, mod);
          F %= mod;
          F = F * j;
          ret += F;
          ret %= mod;
          ret += solve2(i + 1, 3, mask2);
          ret %= mod;
        }
        ret %= mod;
      }
    }
  } else {
    for (int j = 0; j < 10; j++) {
      int mask2 = mask | (1 << j);
      if (j == 0 && mask == 0) mask2 = 0;
      long long R = memo[i + 1][3][mask2];
      R %= mod;
      long long F = R * bigmod(10, 17 - i, mod);
      F %= mod;
      F = F * j;
      ret += F;
      ret %= mod;
      ret += solve2(i + 1, 3, mask2);
      ret %= mod;
    }
  }
  ret %= mod;
  return ret;
}
int main() {
  memset(memo, -1, sizeof(memo));
  memset(memo2, -1, sizeof(memo2));
  for (int i = 0; i < 5000; i++) {
    int x = i;
    for (int j = 0; j < 10; j++) {
      if (x & (1 << j)) cnt[i]++;
    }
  }
  cin >> A >> B >> k;
  while (A.length() < 18) {
    A = '0' + A;
  }
  while (B.length() < 18) {
    B = '0' + B;
  }
  solve(0, 0, 0);
  cout << solve2(0, 0, 0) % mod;
}

```