#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
#define PIL pair<int,LL>
#define PLI pair<LL,int>
#define PIII pair<int,PII>
#define PLL pair<LL,LL>
#define PLII pair<LL,PII>
#define VI vector<int>
#define VVI vector<VI>
#define VL vector<LL>
#define VVL vector<VL>
#define VPII vector<PII>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
#define all(x) x.begin(),x.end()
#define watch(x) cout<<(#x)<<" = "<<(x)<<'\n'
#define mset(a,v) memset(a,v,sizeof(a))
#define setp(x) cout<<fixed<<setprecision(x)
#define EPS 0.00000000001
#define PI acos(-1)
#define loop(i,b,n) for(int i=b;i<n;++i)
#define rev_loop(i,b,n) for(int i=b;i>=n;--i)
using namespace std;

const int MOD = 1e9 + 7;
const LL MX = 1e9;
const LL INF = 1e9;

int main()
{
    //ofstream out("output.txt");
    //ifstream in("input.txt");
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n;
    cin>>n;
    int a[n], mx = 0;
    loop(i,0,n)
    {
        cin>>a[i];
        mx = max(mx,a[i]);
    }

    int mxc = 0, c, ans;
    loop(i,2,mx+1)
    {
        c = 0;
        loop(j,0,n)
        {
            if(a[j] % i == 0) ++c;
        }

        if(c > mxc) {mxc = c; ans = i;}
    }

    cout<<ans<<'\n';

    return 0;
}

#include <bits/stdc++.h>          
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repp(i, st, en) for (ll i = (ll)st; i < (ll)(en); i++)
#define repm(i, st, en) for (ll i = (ll)st; i >= (ll)(en); i--)
#define all(v) v.begin(), v.end()
void chmax(ll &x, ll y) {x = max(x,y);}
void chmin(ll &x, ll y) {x = min(x,y);}
void Yes() {cout << "Yes" << endl; exit(0);}
void No() {cout << "No" << endl; exit(0);}
template<class in_Cout> void Cout(in_Cout x) {cout << x << endl; exit(0);}
template<class in_vec_cout>
void vec_cout(vector<in_vec_cout> vec) {
    for (in_vec_cout res : vec) {cout << res << " ";}
    cout << endl;
}

const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll d = 16;

ll dp[220000][2][17];

ll to_num(char c) {
    ll x = c - '0';
    if (0<=x && x<10) return x;
    ll y = c - 'A';
    return 10 + y;
}

ll bitcnt(ll bit) {
    ll res = 0;
    rep(i,d) if ((bit>>i)&1) res++;
    return res;
}

void addmodp(ll &x, ll y) {x = (x + y) % mod;}

int main() {
    string str; cin >> str;
    ll N = str.size();
    ll K; cin >> K;
    vector<ll> S(N);
    rep(i,N) S[i] = to_num(str[i]);

    ll bit = 1<<S[0];
    dp[0][0][1] = 1LL;
    dp[0][1][1] = S[0] - 1;
    for (ll i=1; i<N; i++) {
        ll from = bitcnt(bit);
        bit |= 1<<S[i];
        ll now = bitcnt(bit);
        dp[i][0][now] = 1;
        for (ll j=1; j<=d; j++) {
            addmodp(dp[i][1][j], dp[i-1][1][j] * j % mod);
            addmodp(dp[i][1][j], dp[i-1][1][j-1] * (d-j+1) % mod);
        }
        rep(j,S[i]) {
            if ((bit>>j)&1) addmodp(dp[i][1][from],1LL);
            else addmodp(dp[i][1][from+1],1LL);
        }
        addmodp(dp[i][1][1],15);
    }

    ll ans = 0LL;
    rep(i,2) addmodp(ans,dp[N-1][i][K]);
    Cout(ans);
}