// In the name of God.
// You are anything and We're nothing
// Ya ali!

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct Node {
    int id;
    Node* l;
    Node* r;
    ll cnt;
    uint8_t h;
    unordered_map<uint8_t, Node*> jump_cache;

    Node* replace_left(uint8_t depth, Node* replace);

    Node* replace_right(uint8_t depth, Node* replace);

    Node* get_left(uint8_t depth);

    Node* get_right(uint8_t depth);

    Node* jump(uint8_t j);

    string print();
};

struct PairHasher {
    ll operator()(const pair<int, int> &p) const {
        return (ll) p.first << 32 | p.second;
    }
};

//map<pair<int, int>, Node*> cache;
unordered_map<pair<int, int>, Node*, PairHasher> cache;

Node* get_node(Node* l, Node* r) {
    auto[it, inserted] = cache.insert({{l->id, r->id}, nullptr});
    if (!inserted)
        return it->second;
//    if (!(cache.size() & (cache.size() - 1)))
//        cerr << cache.size() << '\n';
//    static int created_2 = 0;
//    if (l->h == 2) {
//        cerr << created_2 << " # " << l->print()+r->print() << '\n';
//        ++created_2;
//    }
    assert(l->h == r->h);
    return it->second = new Node{cache.size() - 1, l, r, l->cnt + r->cnt, l->h + 1};
}

Node* base_nodes[2];

Node* get_node(uint8_t h, uint16_t mask) {
    if (!h)
        return base_nodes[mask];
    int w = 1 << h - 1;
    return get_node(get_node(h - 1, mask >> w), get_node(h - 1, mask & (1 << w) - 1));
}

Node* get_zero_node(uint8_t h) {
    if (!h)
        return base_nodes[0];
    Node* pre = get_zero_node(h - 1);
    return get_node(pre, pre);
}

Node* Node::replace_left(uint8_t depth, Node* replace) {
    return !depth ? replace : get_node(l->replace_left(depth - 1, replace), r);
}

Node* Node::replace_right(uint8_t depth, Node* replace) {
    return !depth ? replace : get_node(l, r->replace_right(depth - 1, replace));
}

Node* Node::get_right(uint8_t depth) {
    return !depth ? this : r->get_right(depth - 1);
}

Node* Node::get_left(uint8_t depth) {
    return !depth ? this : l->get_left(depth - 1);
}

Node* Node::jump(uint8_t j) {
    assert(j <= h - 2);
    if (jump_cache.count(j))
        return jump_cache[j];
    assert(h > 2);
    Node* center = get_node(l->r, r->l);
    if (j == h - 2) {
        center = center->jump(j - 1);
        return jump_cache[j] = get_node(get_node(l->jump(j - 1), center)->jump(j - 1),
                                        get_node(center, r->jump(j - 1))->jump(j - 1));
    }
    center = center->jump(j);
    return jump_cache[j] = get_node(get_node(l->jump(j)->r, center->l), get_node(center->r, r->jump(j)->l));
}

string Node::print() {
    if (!h)
        return to_string(cnt);
    return l->print() + r->print();
}

int next(int mask) {
    int ans = 0;
    for (int i = 1; i < 3; ++i) {
        int cur = (mask >> i + 1 & 1) * 4 + (mask >> i & 1) * 2 + (mask >> i - 1 & 1);
        ans |= (cur == 1 || cur == 2 || cur == 3 || cur == 5 || cur == 6) << i;
    }
    return ans >> 1;
}

void init() {
    for (int i = 0; i < 2; ++i)
        base_nodes[i] = new Node{i, nullptr, nullptr, i, 0};
    cache[{-1, 0}] = nullptr;
    cache[{-1, 1}] = nullptr;
    for (int mask = 0; mask < 16; ++mask) {
        get_node(2, mask)->jump_cache[0] = get_node(1, next(mask));
//        cerr << get_node(2, mask)->print() << '\n';
//        cerr << get_node(2, mask)->jump(0)->print() << '\n' << '\n';
    }

}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    init();
//    return 0;
    Node* node;
    {
        string s;
        cin >> s;
        bitset<16> b(string(s.begin(), s.end()));
        node = get_node(4, b.to_ulong());
    }
    ll k;
    cin >> k;
    for (int step = 0; step < 60; ++step)
        if (k >> step & 1) {
            do {
                node = get_node(get_node(get_zero_node(node->h - 1), node->l),
                                get_node(node->r, get_zero_node(node->h - 1)));
                node = get_node(get_node(get_zero_node(node->h - 1), node->l),
                                get_node(node->r, get_zero_node(node->h - 1)));
            } while (node->h - 3 <= step);
//            cerr << node->print() << '\n';
            node = node->jump(step);
//            cerr << node->print() << '\n';
        }
//    cerr << node->print() << '\n';
    cout << node->cnt << '\n';
}