#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define DIV 1000000007 //10^9+7
#define INF LONG_MAX/3
#define bit(n) (1LL<<(n))

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


string S;
ll K;

ll memo[200005][20];

ll get(ll idx, ll num) {
	if(memo[idx][num] >= 0) return memo[idx][num];

	if(idx == S.size()) {
		if(num == K) return 1;
		return 0;
	}


	ll newnum = 16 - num;
	ll ret = 0;
	//同じのとる
	ret += num * get(idx+1, num);
	ret %= DIV;

	//新しいのとる
	if(newnum > 0) {
		ret += newnum * get(idx+1, num + 1);
		ret %= DIV;
	}
	memo[idx][num] = ret;
	return ret;
}

ll getnum(char ch) {
	if(ch >= '0' && ch <= '9') return ch - '0';
	return ch - 'A' + 10;
}


int main(){
	cin >> S >> K;

	ll ans = 0;
	set<ll> done;

	rep(i, 200005) rep(j, 20) memo[i][j] = -1;

	rep(idx, S.size()) {
		ll num = getnum(S[idx]);

		//ここまで0でここから始まる場合
		if(idx != 0) {
			ans += 15 * get(idx + 1, 1);
			ans %= DIV;
		}

		//ここまで一致してきてここから下回る場合
		ll start = 0;
		if(idx == 0) start = 1;
		for(ll n = start; n < num; n++) {
			if(done.count(n)) {
				ans += get(idx + 1, done.size());
			} else {
				ans += get(idx + 1, done.size() + 1);
			}
			ans %= DIV;
		}

		done.insert(num);
	}
	if(done.size() == K) ans++;


	cout << ans % DIV << endl;
}

#include <bits/stdc++.h>
using namespace std;
/*
#include <atcoder/all>
using namespace atcoder;
using mint = modint1000000007;
*/
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define endl "\n"

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}
ll mod_pow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }

const int mod = 1e9 + 7;

void solve() {
    ll N, K;
    cin >> N >> K;

    vector<vector<ll>> dp(4, vector<ll>(3 * N + 1));
    dp[0][0] = 1;
    for (int i = 0; i < 3; i++) {
        vector<ll> imos(3 * N + 2);
        for (ll j = 0; j <= 3 * N; j++) {
            ll l = min(3 * N + 1, j + 1);
            ll r = min(3 * N + 1, j + N + 1);
            imos[l] += dp[i][j];
            imos[r] -= dp[i][j];
        }
        ll now = 0;
        for (int j = 0; j < 3 * N + 1; j++) {
            now += imos[j];
            dp[i + 1][j] = now;
        }
    }

    vector<ll> acc(3 * N + 2);
    for (ll i = 0; i < 3 * N + 1; i++) {
        acc[i + 1] = acc[i] + dp[3][i];
    }

    ll ok = 0;
    ll ng = 3 * N + 1;
    while (ng - ok > 1) {
        ll c = (ok + ng) / 2;
        if (acc[c + 1] < K) {
            ok = c;
        } else {
            ng = c;
        }
    }

    ll sum = ng;
    ll rest = K - acc[ng];
    for (ll i = 1; i <= N; i++) {
        if (rest > dp[2][sum - i]) {
            rest -= dp[2][sum - i];
        } else {
            for (ll j = 1; j <= N; j++) {
                if (rest > dp[1][sum - i - j]) {
                    rest -= dp[1][sum - i - j];
                } else {
                    ll k = sum - i - j;
                    cout << i << " " << j << " " << k << endl;
                    return;
                }
            }
        }
    }
}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();
}