#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
// head
const LL MOD=1e9+7;
const int N=2e5+5;
int k,d[N];
LL dp[N][17];
string s;
int get(char c) {
    if(isdigit(c)) return c-'0';
    else return c-'A'+10;
}
LL dfs(int x,int st,bool a,bool b) {
    if(x==SZ(s)) return !a&&d[st]==k;
    if(!a&&!b&&dp[x][d[st]]!=-1) return dp[x][d[st]];
    int mx=b?get(s[x]):15;
    LL ret=0;
    for(int i=0;i<=mx;i++) {
        if(a&!i&&d[st|(1<<i)]>k) continue;
        ret=(ret+dfs(x+1,(a&!i)?0:st|(1<<i),a&!i,b&(i==mx)))%MOD;
    }
    if(!a&&!b) dp[x][d[st]]=ret;
    return ret;
}
int main() {
    cin>>s>>k;
    for(int i=0;i<1<<16;i++) d[i]=__builtin_popcount(i);
    memset(dp,-1,sizeof dp);
    cout<<dfs(0,0,true,true)<<'\n';
    return 0;
}
/*  -*- coding: utf-8 -*-
 *
 * f.cc: F - Digits Paradise in Hexadecimal
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 200000;
const int MOD = 1000000007;

/* typedef */

typedef long long ll;

/* global variables */

char s[MAX_N + 4];
int dp[MAX_N + 1][17];
bool used[16];

/* subroutines */

inline int hex2dec(char c) {
  return (c >= '0' && c <= '9') ? (c - '0') : (c - 'A' + 10);
}

inline void addmod(int &a, int b) { a = (a + b) % MOD; }
inline int pmod(int a, int b) { return (int)((ll)a * b % MOD); }

/* main */

int main() {
  int k;
  scanf("%s%d", s, &k);
  int n = strlen(s);

  int s0 = hex2dec(s[0]);
  dp[1][1] = s0 - 1;
  used[s0] = true;
  int c = 1;
  
  for (int i = 1; i < n; i++) {
    for (int j = 1; j <= 16; j++)
      if (dp[i][j] > 0) {
	addmod(dp[i + 1][j], pmod(dp[i][j], j));
	if (j < 16)
	  addmod(dp[i + 1][j + 1], pmod(dp[i][j], 16 - j));
      }

    int si = hex2dec(s[i]), e0 = 0, e1 = 0;
    for (int j = 0; j < si; j++) {
      if (used[j]) e0++;
      else e1++;
    }
    addmod(dp[i + 1][c], e0);
    if (c < 16) addmod(dp[i + 1][c + 1], e1);

    addmod(dp[i + 1][1], 15);

    if (! used[si])
      used[si] = true, c++;
  }

  addmod(dp[n][c], 1);

  printf("%d\n", dp[n][k]);
  return 0;
}
