#include <bits/stdc++.h>
using namespace std;
long long INF = 1000000000000000000;
template<const int MOD> struct modint{
    long long val;
    modint(): val(0) {}
    modint(long long x){
        if(x < 0) val = x % MOD + MOD;
        else val = x % MOD;
    }
    modint(const modint &t){
        val = t.val;
    }
    modint& operator =(const modint m){
        val = m.val;
        return *this;
    }
    modint operator -(){
        return modint(-val);
    }
    modint& operator-=(const modint &m){
        val -= m.val;
        if(val < 0) val += MOD;
        return *this;
    }
    modint& operator+=(const modint &m){
        val += m.val;
        if(val >= MOD) val -= MOD;
        return *this;
    }
    modint& operator*=(const modint &m){
        val *= m.val;
        val %= MOD;
        return *this;
    }
    modint& operator/=(modint m){
        *this *= m.inv();
        return *this;
    }
    modint& inv(){
        long long x = 1, y = 0;
        long long a = val, b = MOD;
        while(b != 0){
            long long t = a / b;
            a -= t * b;
            x -= t * y;
            swap(a, b);
            swap(x, y);
        }
        val = x % MOD;
        if(val < 0) val += MOD;
        return *this;
    }
    modint pow(long long k){
        long long res = 1;
        long long v = val;
        while(k > 0){
            if(k & 1) res = res * v % MOD;
            v = v * v % MOD;
            k >>= 1;
        }
        return modint(res);
    }
    modint operator==(const modint &m){
        return val == m.val;
    }
    modint operator+(const modint &m){
        return modint(*this) += m;
    }
    modint operator-(const modint &m){
        return modint(*this) -= m;
    }
    modint operator*(const modint &m){
        return modint(*this) *= m;
    }
    modint operator/(const modint &m){
        return modint(*this) /= m;
    }
};
const int MOD = 1000000007;
using mint = modint<MOD>;
int main(){
    string S;
    int K;
    cin >> S >> K;
    int N = S.size(); 
    vector<vector<mint>> dp(17, vector<mint>(N));
    int bit = 0;
    for(int i = 0; i < N; i++){
        if(S[i] >= 'A') bit |= (1 << (S[i] - 'A' + 10));
        else bit |= (1 << (S[i] - '0'));
    }
    int cnt = __builtin_popcount(bit);
    mint ans = 0;
    if(cnt == K) ans += 1;
    if(S[0] == '1') dp[0][0] = 1;
    else{
        dp[0][0] = 1;
        if(S[0] >= 'A') dp[1][0] = S[0] - 'A' + 9;
        else dp[1][0] = S[0] - '1';
    }
    bit = 0;
    if(S[0] >= 'A') bit |= (1 << (S[0] - 'A' + 10));
    else bit |= (1 << (S[0] - '0'));
    for(int i = 1; i < N; i++){
        int bit2 = 0;
        int ma = 0;
        if(S[i] >= 'A') ma = (S[i] - 'A' + 10);
        else ma = (S[i] - '0');
        for(int j = 0; j < ma; j++){
            bit2 |= (1 << j);
        }
        int temp = ((bit & bit2) ^ bit2);
        int cnt = __builtin_popcount(temp);
        int now = __builtin_popcount(bit);
        if(now == 16) dp[now][i] += ma;
        else {
            dp[now + 1][i] += cnt;
            dp[now][i] += ma - cnt;
        }
        bit |= (1 << ma);
        for(int j = 0; j < 17; j++){
            if(j == 0){
                dp[j + 1][i] += dp[j][i - 1] * 15;
                dp[j][i] = 1;
            }
            else if(j < 16){
                dp[j + 1][i] += dp[j][i - 1] * (16 - j);
                dp[j][i] += dp[j][i - 1] * j;
            }
            else{
                dp[j][i] += dp[j][i - 1] * j;
            }
        }
    }
    ans += dp[K][N - 1];
    cout << ans.val << endl;
}
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define gcd __gcd
#define FOR(i, a, b) for (int i = a; i <= (b); i++)
#define ROF(i, a, b) for (int i = a; i >= (b); i--)
#define pb(x) push_back(x)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define fir first
#define sec second
typedef long long ll;
typedef long double ld;
const ll mod =  1e9 + 7;
const double PI = acos(-1.0);
const double eps = 1e-10;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int maxn = 100005;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >> n;
    vector<int> ans;
    vector<ll> fib(100);
    fib[1] = fib[2] = 1;
    FOR(i, 3, 90) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    int k = 0;
    map<int, bool> mp;
    ROF(i, 90, 1) {
        if(n >= fib[i]) {
            n -= fib[i];
            k = max(k, i);
            mp[i] = true;
        }
    }
    int cur = 3;
    ROF(i, k, 1) {
        cur ^= 1;
        ans.pb(cur);
        if(mp[i]) {
            if(cur == 2) {
                ans.pb(0);
            }
            else {
                ans.pb(1);
            }
        }
    }
    cout << ans.size() << endl;
    for(auto x: ans) {
        if(k % 2) cout << x + 1<< endl;
        else cout << (x^1) + 1 << endl;
    }
	return 0;
}