// ＵＴＦ−８

#include<bits/stdc++.h>

using namespace std;
using ll = long long int;
using lc = complex<ll>;

/* #include<atcoder/all> */
/* using namespace atcoder; */

template<class T>bool chmax(T &a, const T &b) { return (a<b ? (a=b,1) : 0); }
template<class T>bool chmin(T &a, const T &b) { return (a>b ? (a=b,1) : 0); }

int main(void) {
    constexpr ll MOD = 1 ? 1e9+7 : 998244353;
    const double PI = acos(-1);
    constexpr double eps = 1e-10;
    cout << fixed << setprecision(32);
    cin.tie(0); ios::sync_with_stdio(false);

    auto f = [&](char x) {
        if('0' <= x && x <= '9')
            return x - '0';
        return x - 'A' + 10;
    };

    if(1) {
        string n;
        ll k;
        cin >> n >> k;
        ll s = n.size();

        vector<vector<ll>> dq(s, vector<ll>(16+1)); // dp ぴったし, dq 未満
        dq[0][0] = 1;
        dq[0][1] = n[0] == '1' ? 0 : (f(n[0]) - 1);

        set<ll> v;
        v.insert(f(n[0]));
        for(ll i=1; i<s; i++) {
                (dq[i][0] += (dq[i-1][0])) %= MOD;
            for(ll j=0; j<=16; j++) {
                (dq[i][j] += (j * dq[i-1][j])) %= MOD;
                if(j == 0)
                    (dq[i][j+1] += ((15-j) * dq[i-1][j])) %= MOD;
                else if(j < 16)
                    (dq[i][j+1] += ((16-j) * dq[i-1][j])) %= MOD;
            }
            for(ll j=0; j<f(n[i]); j++) {
                (dq[i][v.size() + !v.count(j)] += 1) %= MOD;
            }
            v.insert(f(n[i]));
        }
        ll r = dq[s-1][k] + (v.size() == k);
        cout << (r % MOD) << endl;
    }

    return 0;
}


#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 60
#define INF 1000000005
#define INFLL (ll)1000000000000000005
#define PI 3.1415926535897
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
#define per(a,mod) ((a)%(mod)+(mod))%(mod)
typedef pair<int,int> P;
const int MAX = (1<<20);
const int MOD = 998244353;

int par[MAX];
int depth[MAX];
int siz[MAX];
//初期化
void init(){
    for(int i=0;i<MAX;i++){
        par[i]=i;
        siz[i]=1;
    }
}
//根を探索　
int root(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=root(par[x]);
    }
}

//統合
void unit(int x,int y){
    x=root(x);
    y=root(y);
    if(x==y)return;
    if(depth[x]>depth[y])swap(x,y);
    par[x]=y;
    siz[y]+=siz[x];
    if(depth[x]==depth[y])depth[x]++;
}
// 同じ集合か判定
bool issame(int x,int y){
    return root(x)==root(y);
}

//集合の大きさ
int size(int x){
    return siz[root(x)];
}
bool ext[MAX];
int modPow(long long a, long long n) {
    if(n==0)return 1;
  if (n == 1) return a % MOD;
  if (n % 2 == 1) return (a * modPow(a, n - 1)) % MOD;
  long long t = modPow(a, n / 2);
  return (t * t) % MOD;
}
void solve(){
    int n;
    cin>>n;
    init();
    REP(i,n){
        int f;
        cin>>f;
        f--;
        unit(i,f);
        ext[f]=1;
    }
    map<int,int>mp;
    REP(i,n){
        if(!ext[i])continue;
        mp[root(i)]++;
    }
    int ans=modPow(2,SZ(mp))-1;
    if(ans<0)ans+=MOD;
    OUT(ans);

}
int main(){
    solve();
    return 0;
}
