Строку фибоначчи f(k) для натуральных чисел k определим так: f(1) = 'a', f(2) = 'b', f(k) = f(k - 1) + f(k - 2) при k > 2, где "+" означает конкатенацию строк. требуется найти количество вхождений строки s, состоящей из символов a и b, в строку фибоначчи f(n).

ограничения: длина s от 1 до 25, 1 < = n < = 45.

примечание. длина f(45) равна 1 134 903 170.

входные данные
в первой строке содержится число n, во второй - строка s.

выходные данные
выводится одно число - количество вхождений строки s в строку фибоначчи f(n).

Небольшое наблюдение: если Денис может использовать ровно M лопастей, то он может использовать их так, чтобы четырёхлопастных спиннеров было не больше двух. (Если их три или больше, то каждые три четырёхлопастных спиннера можно поменять на 4 трёхлопастных).

Код (C++)
#include <iostream>
int main() {
    long long M;
    std::cin >> M;
    for (int f = 0; f < 3 && f * 4 <= M; f++) {
        if ((M - f * 4) % 3 == 0) {
            std::cout << (M - f * 4) / 3 << " " << f;
            return 0;
        }
    }
    std::cout << "0 0";
    return 0;
}

Небольшое наблюдение: если Денис может использовать ровно M лопастей, то он может использовать их так, чтобы четырёхлопастных спиннеров было не больше двух. (Если их три или больше, то каждые три четырёхлопастных спиннера можно поменять на 4 трёхлопастных).

Код (C++)
#include <iostream>
int main() {
    long long M;
    std::cin >> M;
    for (int f = 0; f < 3 && f * 4 <= M; f++) {
        if ((M - f * 4) % 3 == 0) {
            std::cout << (M - f * 4) / 3 << " " << f;
            return 0;
        }
    }
    std::cout << "0 0";
    return 0;
}