#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=1000000007;
char str[200010];
LL ans,f[200010][20];
int Len,K,cnt[20],app,tran[123];
int main()
{
	scanf("%s%d",str+1,&K);
	Len=strlen(str+1);
	tran['0']=0;tran['1']=1;tran['2']=2;tran['3']=3;
	tran['4']=4;tran['5']=5;tran['6']=6;tran['7']=7;
	tran['8']=8;tran['9']=9;tran['A']=10;tran['B']=11;
	tran['C']=12;tran['D']=13;tran['E']=14;tran['F']=15;
	for(int i=1;i<=Len;i++){
		f[i][0]=1;//前导零
		for(int j=0;j<=16;j++){
			f[i][j]=(f[i][j]+f[i-1][j]*j)%mod;
			if(j<16)
				f[i][j+1]=f[i-1][j]*(16-j-(j==0))%mod;
		}
		for(int j=(i==1)?1:0;j<tran[int(str[i])];j++)
			f[i][app+(cnt[j]==0)]=(f[i][app+(cnt[j]==0)]+1)%mod;
		if(cnt[tran[int(str[i])]]==0)app++;
		cnt[tran[int(str[i])]]++;
	}
	cout<<(f[Len][K]+(app==K))%mod<<'\n';
}
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int prime[N], mu[N], cnt;

bool st[N];

void init() {
  mu[1] = 1;
  for (int i = 2; i < N; i++) {
    if (!st[i]) {
      prime[++cnt] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
      st[i * prime[j]] = 1;
      if (i % prime[j] == 0) {
        break;
      }
      mu[i * prime[j]] = -mu[i];
    }
  }
}

long long calc(int n, int m) {
  if (!n || !m) {
    return 0;
  }
  if (n > m) {
    swap(n, m);
  }
  long long ans = 0; 
  for (int i = 1; i <= n; i++) {
    ans += 1ll * (n / i) * (m / i) * mu[i];
  }
  for (int i = 1; i <= n; i++) {
    ans += m / i;
  }
  for (int i = 1; i <= m; i++) {
    ans += n / i;
  }
  ans -= n;
  ans -= m;
  ans -= min(n, m);
  ans += 1;
  return 1ll * n * m - ans;
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  int l, r;
  scanf("%d %d", &l, &r);
  init();
  printf("%lld\n", calc(r, r) + calc(l - 1, l - 1) - 2 * calc(l - 1, r));
  return 0;
}