//{{{
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using VLL = vector<LL>;
using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
#ifdef LOCAL
#include "prettyprint.hpp"
// clang-format off
void _print() { cerr << "]\033[0m\n"; }
template <typename T> void __print(T x) { cerr << x; }
template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#define debug(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m["; _print(x)
#define debug_arr(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m" << (x) << "\033[0m\n"
#else
#define debug(x...)
#define debug_arr(x...)
#endif
// clang-format on
//}}}

int k;
int n;
string s;

const int mod = 1e9 + 7;
inline int ch2dig(char ch)
{
    if (ch >= 'A' && ch <= 'F') return ch - 'A' + 10;
    return ch - '0';
}

const int N = 2e5 + 10;
LL dp[N][20];
LL cnt[N];

LL dfs(int pos, int st, bool bound, bool zeros)
{
    if (pos == -1) return __builtin_popcount(st) == k;

    LL ret = 0;
    if (bound && zeros)
    {
        int ed = bound ? ch2dig(s[pos]) : 15;
        for (int i = 0; i <= ed; i++)
        {
            int new_st = st;
            if (i) new_st |= (1 << i);

            ret += dfs(pos - 1, new_st, bound && i == ed, zeros && i == 0);
            ret %= mod;
        }
        debug(pos, st, bound, zeros, ret);
        return ret;
    }

    if (bound && !zeros)
    {
        int ed = bound ? ch2dig(s[pos]) : 15;
        for (int i = 0; i <= ed; i++)
        {
            int new_st = st | (1 << i);

            ret += dfs(pos - 1, new_st, bound && i == ed, 0);
            ret %= mod;
        }
        debug(pos, st, bound, zeros, ret);
        return ret;
    }

    if (!bound && zeros)
    {
        for (int i = 0; i <= 15; i++)
        {
            int new_st = st;
            if (i) new_st |= (1 << i);

            ret += dfs(pos - 1, new_st, 0, zeros && i == 0);
            ret %= mod;
        }
        debug(pos, st, bound, zeros, ret);
        return ret;
    }

    if (dp[pos][__builtin_popcount(st)] != -1) return dp[pos][__builtin_popcount(st)];
    if (!bound && !zeros)
    {
        for (int i = 0; i <= 15; i++)
        {
            int new_st = st | (1 << i);

            ret += dfs(pos - 1, new_st, 0, 0);
            ret %= mod;
        }
    }
    debug(pos, st, bound, zeros, ret);
    return dp[pos][__builtin_popcount(st)] = ret;
}

int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> s >> k)
    {
        clr(dp, -1);
        n = sz(s);
        reverse(all(s));

        LL ans = dfs(n - 1, 0, 1, 1);
        cout << ans << endl;
    }

    return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)

const int P = 1e9 + 7;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int N = 3e6 + 10;

int main()
{
	IOS;
	int n;
	string str;
	vector<int> v;
	cin >> str >> n;

	for(auto x : str)
		if(x >= '0' && x <= '9') v.push_back((int)(x - '0'));
		else v.push_back((int)(10 + x - 'A'));
	
	vector<vector<int> > f(str.size() + 1, vector<int>(18, 0));
	
	int state = 0;
	for(int i = 0; i < (int)str.size(); ++ i)
	{
		for(int j = 1; j <= 16; ++ j)
		{
			f[i + 1][j] = (f[i + 1][j] + (LL)f[i][j] * j % P) % P;
			f[i + 1][j + 1] = (f[i + 1][j + 1] + (LL)f[i][j] * (16 - j) % P) % P;
		}
		f[i + 1][1] = (f[i + 1][1] + (LL)f[i][0] * 15 % P) % P;
		f[i + 1][0] = (f[i + 1][0] + f[i][0]) % P;
		for(int j = 0; j < v[i]; ++ j)
		{
			int nstate = state;
			if(i || j) nstate |= (1 << j);
			f[i + 1][__builtin_popcount(nstate)] += 1;
		}
		state |= (1 << v[i]);
	}

	int res = f[str.size()][n] + (__builtin_popcount(state) == n);
	cout << res << endl;
	
	return 0;
} 