#include <iostream>
#include <vector>
using namespace std;

#define repeat(i, n) for (int i = 0; i < (int)(n); i++)

using int64 = long long;

namespace {

void solve() {
    int n;
    int64 X;
    cin >> n >> X;

    vector<int64> as(n), ubs(n), xs(n);
    repeat (i, n) cin >> as[i];
    repeat (i, n - 1) ubs[i] = as[i + 1] / as[i];
    ubs[n - 1] = 1e18;

    for (int i = n - 1; i >= 0; i--) {
        xs[i] = X / as[i];
        X %= as[i];
    }

    vector<int64> dp(2, 0);
    dp[0] = 1;
    repeat (i, n) {
        vector<int64> next(2, 0);
        repeat (j, 2) repeat (nj, 2) {
            // x + z + j = y + as[i] * nj
            // z = as[i] * nj - x - j
            int64 z = ubs[i] * nj - xs[i] - j;
            if (0 <= z && z < ubs[i]) {
                next[nj] += dp[j];
            }
            // y = x + j - as[i] * nj
            int64 y = xs[i] + j - ubs[i] * nj;
            if (0 < y && y < ubs[i]) {
                next[nj] += dp[j];
            }
        }
        swap(dp, next);
    }
    cout << dp[0] << endl;
}

}

int main() {
    solve();

    return 0;
}
#include <iostream>
#include <string>
using namespace std;
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <set>
#include <map>
#include <cassert>
#define MOD1 1000000007
#define MOD2 998244353
#define LIMIT1 200010
#define LIMIT2 500010
#define LIMIT3 1000010
#define INF ((1<<30)-1)
#define LLINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef long double ld;
typedef const void cv;
typedef pair<ll,ll> P;
#define rep(i,n) for((i)=0;(i)<(n);(i)++)
#define per(i,n) for((i)=(n)-1;(i)>=0;(i)--)
#define ALL(a) (a).begin(),(a).end()
#define ALL2(a, n) (a),(a)+(n)
template<class T,class C> T max(T a,C b){ return std::max(a, (T)b); }
template<class T,class C> T min(T a,C b){ return std::min(a, (T)b); }
#define zt(a,b) (max((a),(b))-min((a),(b)))
#define setpre(n) fixed << setprecision(n)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a/gcd(a,b))*b;}
int dx[8]={1,0,-1,0,1,-1,-1,1},dy[8]={0,1,0,-1,1,1,-1,-1};
ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1){
      res *= a; if(mod>=1) res %= mod;
    }
    a *= a; if(mod>=1) a %= mod;
    n >>= 1;
  }
  return res;
}
void initialize(){
  
}
ll dp[200010][16]={};
//i桁目まで決め,種類数がj
int main(void){
  initialize();
  ll n,m,i,j,k,result=0;
  int a[LIMIT2]={0};
  string s;
  
  cin >> s >> k;
  n = s.size();
  
  set<char> sc;
  vector<ll> dp2(n+1,0);
  for(i=0;i<n;i++){
    sc.insert(s[i]);
    dp2[i+1] = (ll)sc.size();
  }
  sc.clear();
  string ss="0123456789ABCDEF";
  //dp[1][1] = (ll)(s[0]>='A'?s[0]-'A'+10:s[0]-'0')-1;
  for(i=0;i<n;i++){
    ll tmp = (ll)(s[i]>='A'?s[i]-'A'+10:s[i]-'0');
    //cout << tmp << ' ';
    for(j=(i==0?1:0);j<tmp;j++){
      dp[i+1][dp2[i]+(sc.count(ss[j])?0:1)] += 1;
    }
    sc.insert(s[i]);
  }
  for(i=2;i<=n;i++){
    dp[i][1] += 15;
  }
  for(i=0;i<n;i++){
    for(j=1;j<=k;j++){
      dp[i+1][j] += dp[i][j] * (j);
      dp[i+1][j] %= MOD1;
      dp[i+1][j+1] += dp[i][j] * (16-j);
      dp[i+1][j+1] %= MOD1;
    }
  }
  result = dp[n][k]+(dp2[n]==k?1:0);
  result %= MOD1;
  
  cout << result << endl;
  return 0;
}
