// editorial
#include<iostream>
#include<vector>
#include<numeric>
using namespace std;

typedef long long ll;
const ll mod = 998244353;

ll modpow(ll a, ll b, ll p = 1e9+7){
    if(b == 0)  return 1;

    if(b % 2 == 0){
        ll d = modpow(a, b/2, p);
        return (d*d) % p;
    }else{
        return (a%p * modpow(a, b-1, p)) % p;
    }
}

int main(){
    int n, k;
    cin >> n >> k;
    vector<ll> v(n);
    for(int i = 0; i < n; i++)  cin >> v[i];
    vector<ll> fact(k+1, 1);
    for(int i = 1; i <= k; i++) fact[i] = fact[i-1]*i%mod;
    vector<ll> invf(k+1, 1);
    for(int i = 1; i <= k; i++) invf[i] = modpow(fact[i], mod-2, mod);
    vector<ll> sum(k+1, 0);
    sum[0] = n;
    vector<ll> powers(n, 1);
    for(int i = 1; i <= k; i++){
        for(int j = 0; j < n; j++){
            powers[j] = powers[j]*v[j]%mod;
            (sum[i] += powers[j]*invf[i]%mod) %= mod;
        }
    }
    const ll invtwo = modpow(2, mod-2, mod);
    vector<ll> fpowers(n, 1);
    for(int i = 1; i <= k; i++){
        ll tmp = 0, sub = 0;
        for(int j = 0; j <= i; j++){
            (tmp += sum[j]*sum[i-j]%mod) %= mod;
        }
        (tmp *= fact[i]) %= mod;
        for(int j = 0; j < n; j++){
            fpowers[j] = fpowers[j]*2*v[j]%mod;
            (sub += fpowers[j]) %= mod;
        }
        cout << (tmp-sub+mod)*invtwo%mod << endl;
    }
    return 0;
}
#include <iostream>

using namespace std;
using LL = long long;

const int kM = 1e9 + 7;
const int kB = 16, kMaxN = 2e5 + 1;

string s;
LL f[kMaxN][kB + 1], g[kMaxN][kB + 1];
int c[kB];
int n, k, t, ans;

void check() {
  f[1][1] = kB - 1;
  for (int i = 1; i < n; i++) {
    for (int j = 1; j <= k; j++) {
      f[i][j] = (f[i][j] + f[i - 1][j] * j + f[i - 1][j - 1] * (kB - j + 1)) % kM;
    }
    ans = (ans + f[i][k]) % kM;
  }
}

void chick() {
  g[1][1] = -1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
      g[i][j] = (g[i][j] + g[i - 1][j] * j + g[i - 1][j - 1] * (kB - j + 1)) % kM;
    }
    for (int j = 0; j < s[i - 1]; j++) {
      int tmp = t + !c[j];
      g[i][tmp] = (g[i][tmp] + 1) % kM;
    }
    t += !(c[s[i - 1]]++);
  }
  ans = (ans + g[n][k] + (t == k)) % kM;
}

int main() {
  cin >> s >> k;
  n = s.length();
  for (int i = 0; i < n; i++) {
    s[i] -= s[i] <= '9' ? '0' : 'A' - 10;
  }
  check(), chick();
  cout << ans;
  return 0;
}