#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long count_occurrences(const string& S, const string& P) {
    int n = S.length();
    int m = P.length();
    if (m > n) return 0;

    vector<int> pi(m, 0);
    for (int i = 1, j = 0; i < m; ++i) {
        while (j > 0 && P[i] != P[j]) j = pi[j - 1];
        if (P[i] == P[j]) j++;
        pi[i] = j;
    }

    long long count = 0;
    for (int i = 0, j = 0; i < n; ++i) {
        while (j > 0 && S[i] != P[j]) j = pi[j - 1];
        if (S[i] == P[j]) j++;
        if (j == m) {
            count++;
            j = pi[m - 1];
        }
    }
    return count;
}

long long count_boundary_occurrences(const string& A, const string& B, const string& P) {
    int m = P.length();
    if (m <= 1) return 0;

    int lenA = min((int)A.length(), m - 1);
    int lenB = min((int)B.length(), m - 1);

    string boundary_str = A.substr(A.length() - lenA) + B.substr(0, lenB);
    return count_occurrences(boundary_str, P);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string P;
    int n;

    if (!(cin >> P >> n)) return 0;

    int m = P.length();

    vector<string> F = {"", "b", "a"};

    if (n <= 2) {
        cout << count_occurrences(F[n], P) << "\n";
        return 0;
    }

    int k = 2;
    while (k < n && F[k].length() < 2 * m) {
        k++;
        F.push_back(F[k - 1] + F[k - 2]);
    }

    vector<long long> C(n + 1, 0);

    for (int i = 1; i <= k; ++i) {
        C[i] = count_occurrences(F[i], P);
    }

    if (k == n) {
        cout << C[n] << "\n";
        return 0;
    }

    long long cross1 = count_boundary_occurrences(F[k], F[k - 1], P);
  
    long long cross2 = count_boundary_occurrences(F[k] + F[k - 1], F[k], P);

    for (int i = k + 1; i <= n; ++i) {
        long long cross = ((i - k) % 2 == 1) ? cross1 : cross2;
        C[i] = C[i - 1] + C[i - 2] + cross;
    }

    cout << C[n] << "\n";

    return 0;
}