#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int getRand(int l, int r)
{
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}
  
#define int long long 
#define pb push_back
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define precise(x) fixed << setprecision(x) 

const int MOD = 1e9+7;

int mod_pow(int a,int b,int M = MOD)
{
    if(a == 0) return 0;
    b %= (M - 1);  //M must be prime here
    
    int res = 1;
    
    while(b > 0)
    {
        if(b&1) res=(res*a)%M;
        a=(a*a)%M;
        b>>=1;
    }
    
    return res;
}

const int N = 100;
vector<bool> isprime(N,true);

void solve()
{
   isprime[1] = isprime[0] = 0;
    
   for(int i=2;i<N;i++)
       if(isprime[i])
        for(int j=i+i;j<N;j+=i) isprime[j] = 0;
       
   vector<int> pr;
       
   for(int i=2;i<=72;i++) if(isprime[i]) pr.pb(i);
       
   int l,r;
    cin >> l >> r;
    
   int n = r - l + 1; 
    
   vector<int> a(n);
   f(i,n) a[i] = l + i;
    
   vector<int> mask(n,0);
    
   f(i,n)
   {
       f(j,20) if(a[i] % pr[j] == 0) mask[i] |= (1<<j);
   }
    
   vector<int> cur(1<<20,0),nex(1<<20,0);
   cur[0] = 1;
    
   f(j,n) 
   {
       f(i,(1<<20))
       {
           nex[i] = 0;
       }
       
       f(i,(1<<20))
       {
           nex[i] = cur[i];
       }
       
       f(i,(1<<20))
       {
           if((i & mask[j]) == 0) nex[i | mask[j]] += cur[i];
       }
       
       swap(cur,nex);
   }
    
   cout << accumulate(all(cur),0); 
}

signed main()
{
    fast;
    
    int t = 1;
    
//    cin >> t;
    
    while(t--)
        
    solve();
}

#include<bits/stdc++.h>
using namespace std;
string s;
long long k , diff [300005] , num [300005][20];
long long mod = 1e9 + 7 , dp [200005][3][17] , kk;
map < char , long long > mp;
long long ff ( int x , int on , int dif )
{
    if ( dif > 16 ) return 0;
    if ( x == s . size () )
    {
        if ( dif == k ) return 1;
        else return 0;
    }
    if ( dp [x][on][dif] != -1 ) return dp [x][on][dif];
    long long ans = 0;
    if ( on )
    {
        int eq = mp [ s [x] ];
        for ( int i = 0 ; i <= eq ; i ++ )
        {
            long long last = diff [ x - 1 ];
            if ( x == 0 ) last = 0;
            if ( i < eq )
            {
                if ( num [x][i] == 0 ) ans += ff ( x + 1 , 0 , last + 1 );
                else ans += ff ( x + 1 , 0 , last );
                ans %= mod;
            }
            if ( i == eq ) ans += ff ( x + 1 , 1 , diff [x] );
        }
        ans %= mod;
    }
    else
    {
        ans += ff ( x + 1 , 0 , dif ) * dif;
        ans += ff ( x + 1 , 0 , dif + 1 ) * ( 16 - dif );
        ans %= mod;
    }
    return dp [x][on][dif] = ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    mp ['0'] = 0;
    mp ['1'] = 1;
    mp ['2'] = 2;
    mp ['3'] = 3;
    mp ['4'] = 4;
    mp ['5'] = 5;
    mp ['6'] = 6;
    mp ['7'] = 7;
    mp ['8'] = 8;
    mp ['9'] = 9;
    mp ['A'] = 10;
    mp ['B'] = 11;
    mp ['C'] = 12;
    mp ['D'] = 13;
    mp ['E'] = 14;
    mp ['F'] = 15;
    memset ( dp , -1 , sizeof dp );
    cin >> s >> k;
    for ( int i = 0 ; i < s . size () ; i ++ )
    {
      if ( i )
      {
        for ( int j = 0 ; j <= 16 ; j ++ ) num [i][j] += num [ i - 1 ][j];
      }
        if ( num [i][ mp [ s [i] ] ] == 0 ) kk ++;
        num [i][ mp [ s [i] ] ] ++;
        diff [i] = kk;
    }
    long long add = 0;
    add += ff ( 1 , 1 , diff [0] );
    for ( int i = 1 ; i < mp [ s [0] ] ; i ++ ) add += ff ( 1 , 0 , 1 );
    for ( int i = 1 ; i < s . size () ; i ++ ) add += ff ( i + 1 , 0 , 1 ) * 15;
    cout << add % mod;
}
