#include <bits/stdc++.h>
#define int long long
#define PI pair<int,int>
using namespace std;
const int maxm=2e5+5;
const int mod=1e9+7;
int d[maxm][17][2];
char s[maxm];
int n,k;
int dfs(int len,int st,bool limit,bool pre){
    int cnt=__builtin_popcount(st);
    if(!len)return cnt==k;
    if(d[len][cnt][limit]!=-1)return d[len][cnt][limit];
    int ans=0;
    int ma=(limit?s[len]:15);
    for(int i=0;i<=ma;i++){
        int stt=st;
        if(!pre||i!=0)stt|=(1<<i);
        ans=(ans+dfs(len-1,stt,limit&&i==ma,pre&&i==0))%mod;
    }
    return d[len][cnt][limit]=ans;
}
int solve(){
    return dfs(n,0,1,1);
}
signed main(){
    ios::sync_with_stdio(0);
    //
    memset(d,-1,sizeof d);
    //
    cin>>(s+1)>>k;
    n=strlen(s+1);
    for(int i=1;i<=n;i++){
        if(isdigit(s[i]))s[i]=s[i]-'0';
        else s[i]=s[i]-'A'+10;
    }
    reverse(s+1,s+1+n);
    int ans=solve();
    cout<<ans<<endl;
    return 0;
}
/*

*/

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int r1, c1, r2, c2;
  cin >> r1 >> c1 >> r2 >> c2;
  int r = r2 - r1, c = c2 - c1;
  int ans = 3;
  if (!r && !c)
    ans = 0;
  else if (r == c || r == -c || abs(r) + abs(c) <= 3)
    ans = 1;
  else if ((r ^ c ^ 1) & 1 || abs(r + c) <= 3 || abs(r - c) <= 3 ||
           abs(r) + abs(c) <= 6)
    ans = 2;
  cout << ans << endl;
}