#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, n, a) for (int i = n; i >= a; --i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int, int> PII;
mt19937 rnd(time(0));

inline int in() {
  char ch = getchar();
  int f = 1, x = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-')
      f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
  return f * x;
}

const int inf = (1 << 30);
const int mod = 998244353;
const int N = 400010;

LL ksm(LL a, LL b, LL MOD = mod) {
  LL res = 1;
  while (b) {
    if (b & 1)
      res = res * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}

LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
LL exgcd(LL a, LL b, LL &x, LL &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  LL g = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return g;
}

LL Inv(LL a, LL b = mod) {
  assert(gcd(a, b) == 1);
  a %= b;
  return ksm(a, b - 2, b);
}

LL fac[N], inv[N];

void init(int n) {
  fac[0] = 1;
  rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
  inv[n] = ksm(fac[n], mod - 2);
  per(i, n - 1, 0) inv[i] = inv[i + 1] * (i + 1) % mod;
}

LL C(int n, int m) {
  if (m > n || m < 0)
    return 0;
  return fac[n] * inv[m] % mod * inv[n - m] % mod;
}

int _mu[N], isp[N];
VI p;
void init_prime(int n) {
  _mu[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!isp[i])
      p.push_back(i), _mu[i] = -1;
    for (int j = 0; j < (int)p.size() && i * p[j] <= n; ++j) {
      isp[i * p[j]] = 1;
      if (i % p[j] == 0) {
        _mu[i * p[j]] = 0;
        break;
      }
      _mu[i * p[j]] = -_mu[i];
    }
  }
}

void solve() {
  int n = in(), m = in();
  init(n + m);
  init_prime(n + m);
  LL ans = 0;
  rep(i, 1, m) {
    LL val = 1;
    int w = i;
    for (int j = 0; j < (int)p.size(); ++j) {
      if (p[j] * p[j] > w)
        break;
      int res = 0;
      while (w % p[j] == 0) {
        w /= p[j];
        ++res;
      }
      (val *= C(res + n - 1, n - 1)) %= mod;
    }
    if (w > 1)
      (val *= n) %= mod;
    (ans += val) %= mod;
  }
  printf("%lld\n", ans);
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
  // freopen("out.out", "w", stdout);
#endif
  int T = 1;
  // T = in();
  while (T--) {
    solve();
  }
}

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <climits>
#include <string>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <ctime>
#include <cassert>
#include <fstream>
#include <stack>
#include <random>
#include <iomanip>

#include <fstream>


using namespace std;
typedef long long ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E18;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
dd EPS=1E-9;
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

ll f(char c){
    ll k=c-'0';
    if(0<=k && k<=9){
        return k;
    }
    ll l=c-'A';
    return 10+l;
}

int main(){fastio
    string N;cin>>N;
    ll K;cin>>K;
    ll n;n=(ll)N.size();
    ll dp[2][n][17];
    ll bol[n][16];rep(i,0,n-1)rep(j,0,15)bol[i][j]=0;
    rep(i,0,n-1){
        if(i>0){
            rep(j,0,15){
                bol[i][j]=bol[i-1][j];
            }
        }
        bol[i][f(N[i])]=1;
    }
    /*
    rep(i,0,15){
        rep(j,0,n-1){
            cout<<bol[j][i]<<' ';
        }
        cout<<endl;
    }
    cout<<endl;
     */
    
    rep(i,0,n-1){
        rep(j,1,15){
            bol[i][j] = bol[i][j-1]+bol[i][j];
        }
    }
    /*
    rep(j,0,15){
        rep(i,0,n-1){
            cout<<bol[i][j]<<' ';
        }
        cout<<endl;
    }
    cout<<endl;
    */
    
    //bol[i][j]=0~jのうちN[i]までで現れたものの個数
    rep(i,0,n-1){
        rep(j,0,16){
            if(j==bol[i][15]){
                dp[0][i][j]=1;
            }else{
                dp[0][i][j]=0;
            }
            if(i==0){
                if(j==0){
                    dp[1][i][j]=1;
                }else if(j==1){
                    dp[1][i][j]=f(N[i])-1;
                }else{
                    dp[1][i][j]=0;
                }
            }else{
                if(j==0){
                    dp[1][i][j]=1;
                }else{
                    if(f(N[i]) == 0){
                        if(j==1){
                            dp[1][i][j] = mod(dp[1][i-1][j-1]*(16-j)+dp[1][i-1][j]*j);
                        }else{
                            dp[1][i][j] = mod(dp[1][i-1][j-1]*(17-j)+dp[1][i-1][j]*j);
                        }
                        
                    }else{
                        if(j==1){
                            dp[1][i][j] = mod(dp[1][i-1][j-1]*(16-j)+dp[1][i-1][j]*j);
                        }else{
                            dp[1][i][j] = mod(dp[1][i-1][j-1]*(17-j)+dp[1][i-1][j]*j);
                        }
                        
                        dp[1][i][j] += dp[0][i-1][j]*(bol[i-1][f(N[i])-1]);
                        dp[1][i][j] = mod(dp[1][i][j]);
                        dp[1][i][j] += dp[0][i-1][j-1]*(f(N[i])-bol[i-1][f(N[i])-1]);
                        dp[1][i][j] = mod(dp[1][i][j]);
                    }
                }
            }
        }
    }
    ll ans=0;
    ans += dp[0][n-1][K];
    ans = mod(ans);
    ans += dp[1][n-1][K];
    ans = mod(ans);
    cout<<ans<<endl;
    
    /*
    rep(i,0,15){
        rep(j,0,n-1){
            cout<<bol[j][i]<<' ';
        }
        cout<<endl;
    }
    cout<<endl;
    
    rep(k,0,1){
        cout<<"k: "<<k<<endl;
        rep(j,0,15){
            rep(i,0,n-1){
                cout<<dp[k][i][j]<<' ';
            }
            cout<<endl;
        }
        cout<<endl;
    }
    */
    
    return 0;
    
}





