#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define MOD 998244353
lld DP[10000][10000];

lld calc(int a, int b){
  //cout<<a<<" "<<b<<endl;
  if(a<0 || b<0 || a<b)return 0;
  //out<<a<<" "<<b<<endl;
  if(DP[a][b]!=-1)return DP[a][b];
  //cout<<a<<" "<<b<<endl;
  DP[a][b]=0;
  DP[a][b]+=calc(a-1,b-1);
  DP[a][b]+=calc(a,2*b);
  DP[a][b]%=MOD;
  return DP[a][b];
}
/*lld manual(int a, int b){
  int cnt=0;
  rep(i,0,a+1){
    rep(j,0,a+1){
      rep(k,0,a+1){
	rep(l,0,a+1){
	  rep(m,0,a+1){
	    rep(n,0,a+1){
	    if(i+j+k+l+m+n==a && (i+2*j+4*k+8*l+16*m+32*n)==b*32)cnt++;
	    }
	  }
	}
      }
    }
  }
  return cnt;
}*/
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n,k;
  cin>>n>>k;
  rep(i,0,n+1){
    rep(j,0,n+1){
      DP[i][j]=-1;
      if(i==0)DP[i][j]=0;
      if(j==0)DP[i][j]=0;
    }
  }
  DP[0][0]=1;
  cout<<calc(n,k)<<endl;
  /*rep(i,0,n+1){
    rep(j,0,k+1){
      if(manual(i,j)!=calc(i,j))cout<<i<<" "<<j<<" "<<calc(i,j)<<" "<<manual(i,j)<<endl;
    }
  }*/
  
  return 0;
}
#include<bits/stdc++.h>
#define ll long long
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define N 200005
#define M 1000000007
#define pii pair<ll,ll>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

ll bigmod(ll a,ll n)
{
    if(n==0)
        return 1;
    ll ans=bigmod(a,n/2);
    ans=(ans*ans)%M;
    if(n%2)
        ans=(ans*a)%M;
    return ans;
}
ll f[20];
ll inv[20];

string s;
ll k;
vector<char>all;

ll C(ll n,ll r)
{
    if(n<r)
        return 0;
    return f[n]*inv[r]%M*inv[n-r]%M;
}

ll dp[N][17][17];

ll run(int idx,int k1,int k2)
{
    if(idx==0)
    {
        return k1==0;
    }
    if(dp[idx][k1][k2]!=-1)
        return dp[idx][k1][k2];
    ll ans=0;
    if(k1>0)
    {
        ans+=1LL*k1*run(idx-1,k1-1,k2+1);
        ans%=M;
    }
    if(k2>0)
    {
        ans+=1LL*k2*run(idx-1,k1,k2);
        ans%=M;
    }
    return dp[idx][k1][k2]=ans;
}

int check(string s)
{
    int c=0,f=0;
    set<int>w;
    for(char p:s)
    {
        if(f)
        {
            w.insert(p);
        }
        else if(p!='0')
        {
            w.insert(p);
            f=1;
        }
    }
    return w.size();
}

main()
{
    memset(dp,-1,sizeof dp);
    f[0]=inv[0]=1;
    for(ll i=1; i<20; i++)
    {
        f[i]=f[i-1]*i%M;
        inv[i]=bigmod(f[i],M-2);
    }
    for(char x='0'; x<='9'; x++)
        all.push_back(x);
    for(char x='A'; x<='F'; x++)
        all.push_back(x);

    cin>>s>>k;
    set<char>upto;
    ll ans=0;

    for(ll i=0; i<s.size(); i++)
    {
        ll till=upto.size();
        for(char u:all)
        {
            if(u<s[i])
            {
                if(i==0&&u=='0')
                    continue;
                set<char>temp=upto;
                temp.insert(u);
                ll already=temp.size();
                ll baki=k-already;
                if(baki>=0)
                {
                    ll temp=1;
                    temp*=C(16-already,baki)*run(s.size()-i-1,baki,already);
                    ans+=temp;
                    //cout<<i<<' '<<u<<' '<<temp<<endl;
                    ans%=M;
                }
            }
        }
        upto.insert(s[i]);
    }
    for(ll i=1; i<s.size(); i++)
    {
        for(char u:all)
        {
            if(u=='0')
                continue;
            ll already=1;
            ll baki=k-already;
            if(baki>=0)
            {
                ll temp=1;

                temp*=C(16-already,baki)*run(s.size()-1-i,baki,already);
                ans+=temp;
                //cout<<i<<' '<<u<<' '<<temp<<endl;
                ans%=M;
            }
        }
    }
    if(upto.size()==k) ans++;
    ans%=M;
    cout<<ans;
}
