#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

const int K = 16;
const int MOD = 1e9 + 7;

int add(int a, int b) {
    if (a + b < MOD) {
        return a + b;
    }
    return a + b - MOD;
}

int sub(int a, int b) {
    if (a >= b) {
        return a - b;
    }
    return a - b + MOD;
}

int mul(int a, int b) {
    return 1LL * a * b % MOD;
}

int binpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = mul(res, a);
        }
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}

int divv(int a, int b) {
    return mul(a, binpow(b, MOD - 2));
}

int c[K + 1][K + 1];

void init() {
    for (int i = 0; i <= K; i++) {
        c[i][0] = 1;
        c[i][i] = 1;
        for (int j = 1; j < i; j++) {
            c[i][j] = add(c[i - 1][j], c[i - 1][j - 1]);
        }
    }
}

int C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return c[n][k];
}

vector<int> parse() {
    string s;
    cin >> s;
    vector<int> ans;
    for (auto x : s) {
        if (x <= '9') {
            ans.push_back(x - '0');
        } else {
            ans.push_back(10 + (x - 'A'));
        }
    }
    return ans;
}

int solve(int len, int cnt) {
    vector<int> tmp(cnt + 1);
    for (int i = 1; i <= cnt; i++) {
        tmp[i] = binpow(i, len);
        for (int j = 1; j < i; j++) {
            tmp[i] = sub(tmp[i], mul(tmp[j], C(i, j)));
        }
    }
    return tmp[cnt];
}

int solve(int n, int k, vector<int> cnt) {
    int alr = 0;
    int s = 0;
    for (int i = 0; i < 16; i++) {
        alr += (cnt[i] > 0);
        s += cnt[i];
    }
    if (alr > k) {
        return 0;
    }
    vector<int> tmp(k + 1);
    tmp[alr] = binpow(alr, n - s);
    for (int i = alr + 1; i <= k; i++) {
        // tmp[i] = mul(C(16 - alr, i - alr), binpow(i, n - s));
        // cerr << i << ' ' << tmp[i] << endl;
        tmp[i] = binpow(i, n - s);
        for (int j = alr; j < i; j++) {
            tmp[i] = sub(tmp[i], mul(tmp[j], C(i - alr, j - alr)));
        }
    }
    return mul(tmp[k], C(16 - alr, k - alr));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    init();

    int k;
    vector<int> a;
    a = parse();
    cin >> k;
    int n = (int)a.size();
    int ans = 0;
    for (int len = 1; len < n; len++) {
        {
            int cr = mul(C(15, k), solve(len, k));
            ans = add(ans, cr);
        }
        {
            int cr = mul(C(15, k - 1), solve(len, k));
            cr = mul(cr, divv(k - 1, k));
            ans = add(ans, cr);
        }
    }
    {
        vector<int> cnt(16);
        for (int pref = 0; pref <= n; pref++) {
            if (pref == n) {
                ans = add(ans, solve(n, k, cnt));
            } else {
                for (int j = 0; j < a[pref]; j++) {
                    if (pref == 0 && j == 0) continue;
                    cnt[j]++;
                    ans = add(ans, solve(n, k, cnt));
                    cnt[j]--;
                }
                cnt[a[pref]]++;
            }
        }
    }
    cout << ans << endl;
}

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

#define llong long long 
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#ifdef testing/*{{{*/
mt19937 rng(177013);
#else
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
#endif
#define rand() (int)(rng() >> 1)
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#define SPEC(name) CONCAT(name, __LINE__)
#ifdef LOCAL_DEBUG   
int __db_level = 0;
#define clog cerr << string(__db_level * 2, ' ')
struct debug_block {
    string msg;
    debug_block(const string& s): msg(s) { clog << "{ " << msg << endl; ++__db_level; }
    ~debug_block() { --__db_level; clog << "} " << msg << endl; }
};
#define DB(args...) stringstream SPEC(ss); SPEC(ss)<< args; debug_block SPEC(dbbl)(SPEC(ss).str())
#else
#define clog if (0) cerr
#define DB(...)
#endif
#define db(val) "[" #val " = " << val << "]; "
template<class U, class V> ostream& operator<<(ostream& out, const pair<U, V>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")";
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup);
}
template<class ...U>
ostream& operator<<(ostream& out, const tuple<U...>& tup) { return print_tuple_utils<0, tuple<U...>>(out, tup); }
template<class, typename = void> struct has_const_iterator : false_type {};
template<class T> struct has_const_iterator<T, void_t<typename T::const_iterator>> : true_type {};
template<class T>
typename enable_if<has_const_iterator<T>::value && !is_same<T, string>::value, ostream&>::type
operator<<(ostream& out, const T& container) { 
    auto beg = container.begin(), end = container.end();
    out << "(" << container.size() << ") {";
    if (beg != end) out << *(beg++);
    while (beg != end) out << ", " << *(beg++);
    return out << "}";
}
#define ptrtype(x) typename iterator_traits<x>::value_type
template<class u> vector<ptrtype(u)> $v(u a, u b) { return vector<ptrtype(u)>(a, b); }/*}}}*/
// ACTUAL SOLUTION START HERE ////////////////////////////////////////////////////////////////

void inv(string& a) {
    for (auto& ch: a) ch ^= 'A' ^ 'B';
}

void inv(list<string>& u) {
    for (auto& s: u) inv(s);
}

list<string> concat(list<string> u, const list<string>& v) {
    auto iu = u.begin();
    auto iv = v.begin();
    for (; iu != u.cend(); ++iu, ++iv)
        *iu += *iv;
    return u;
}

int main(void) {
#ifdef LOCAL
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
    freopen(".log", "w", stderr);
#endif
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    list<string> ans = {"AB"};
    for (int i = 2; i <= n; ++i) {
        auto a1 = concat(ans, ans);
        auto x = ans; inv(x);
        auto a2 = concat(ans, x);
        ans = a1;
        ans.splice(ans.end(), a2);
        ans.push_back(string((1 << i >> 1), 'A') + string((1 << i >> 1), 'B'));
    }
    cout << len(ans) << '\n';
    for (auto& s: ans) cout << s << '\n';
    
    return 0;
}

// vim: foldmethod=marker

