#include <bits/stdc++.h>

using namespace std;
	
#define rep(i,a,b) for(int i = a; i < (b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

typedef long long ll;
const int MAX_N = 2e5+5;
const int M = 1e9+7;

inline int addM(ll a,ll b){return (a+b)%M;}
inline int mulM(ll a,ll b){return (a*b)%M;}

int main(){
    cin.tie(0)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
	int k;
	string s;
	cin>>s>>k;
	vector<int> num;
	for(auto c : s){
		if(c>='0' && c<= '9'){
			num.push_back(c-'0');
		}else{
			num.push_back(c-'A'+10);
		}
	}
	int n = sz(s);
	vector<vector<int> > dp(n+1,vector<int>(17));
	set<int> digitSet;
	dp[1][1] = num[0]-1;
	for(int i = 1;i < n;i++){
		digitSet.insert(num[i-1]);
		for(int j = 1;j <= 16;j++){
			dp[i+1][j]=addM(mulM(dp[i][j],j),dp[i+1][j]);
			dp[i+1][j+1]=addM(mulM(dp[i][j],16-j),dp[i+1][j+1]);
		}
		int j = sz(digitSet);
		for(int k = 0 ; k < num[i] ;k++){
			if(digitSet.find(k)!=digitSet.end()){
				dp[i+1][j] = addM(dp[i+1][j],1);
			}else{
				dp[i+1][j+1] = addM(dp[i+1][j+1],1);
			}
		} 
		dp[i+1][1] = addM(dp[i+1][1],15);
	}
	int ans = dp[n][k];
	digitSet.insert(num[n-1]);
	if(sz(digitSet) == k)ans++;
	cout<<ans;
    return 0;

}


#include <iostream>

using namespace std;
using ll = long long;

const int kMod = 1e9 + 7;
const int kMaxN = 2e5 + 1;

string s;
int a[kMaxN];
ll c[20][20], dp[kMaxN][20];
ll ans, k, n, fl, b[20];

ll ksm(ll a, ll b) {
  ll x = 1;
  for (; b; b /= 2, a = a * a % kMod) {
    if (b % 2 == 1) {
      x = x * a % kMod;
    }
  }
  return x;
}

int q() {
  int cnt = 0, i;
  for (i = 0; i <= 15; i++) {
    cnt += (b[i] > 0);
  }
  return cnt;
}
int main() {
  int i, t1, j, l;
  cin >> s;
  n = s.size();
  for (i = 0; i < n; i++) {
    if (s[i] >= 'A') {
      a[i + 1] = s[i] - 'A' + 10;
    } else {
      a[i + 1] = s[i] - '0';
    }
  }
  cin >> k;
  dp[1][1] = a[1] - 1;
  for (i = 1; i < n; i++) {
    dp[i + 1][1] = 15, b[a[i]]++;
    for (j = 1; j <= k; j++) {
      dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * j) % kMod;
      dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * (16 - j)) % kMod;
    }
    t1 = q();
    for (j = 0; j < a[i + 1]; j++) {
      if (b[j] == 0) {
        dp[i + 1][t1 + 1]++;
      } else {
        dp[i + 1][t1]++;
      }
    }
  }
  b[a[n]]++, dp[n][q()]++;
  cout << dp[n][k] % kMod;
  return 0;
}