#define _USE_MATH_DEFIMES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007;
const int MOD2 = 998'244'353;
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

template<class T, class S> inline bool chmax(T &a, const S &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T, class S> inline bool chmin(T &a, const S &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}










int main(){
    int N; long long K; std::cin >> N >> K;
    std::vector<std::vector<long long>> dp(4, std::vector<long long>(3*N + 8));
    dp[0][0] = 1;
    for(int i{0}; i < 3; ++i){
        for(int j{0}, j_len{i*N}; j <= j_len; ++j){
            dp[i+1][j+1] += dp[i][j];
            dp[i+1][j+N+1] -= dp[i][j];
        }
        for(int j{0}, j_len{(i+1) * N}; j < j_len; ++j){
            dp[i+1][j+1] += dp[i+1][j];
        }
    }

    int sm;
    for(int i{3}, i_len{3*N}; i <= i_len; ++i){
        if(K <= dp[3][i]){
            sm = i; break;
        }else{
            K -= dp[3][i];
        }
    }
    for(int i{1}; i <= N; ++i){
        int x{sm - i};
        int jmx{std::min(N, x-1)}, jmn{std::max(x-N, 1)};
        if(jmx < jmn) continue;
        if(K > jmx - jmn + 1){
            K -= jmx - jmn + 1;
            continue;
        }
        int j{int(jmn + K - 1)};
        std::cout << i << " " << j << " " << (x - j) << std::endl;
        return 0;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
const ll mod = 1e9 + 7;
const int maxn = 1e5+5;

void go() {
    int n;
    cin>>n;
    string s = "    ";
    cin>>s[0]>>s[1]>>s[2]>>s[3];
    if (n==2) {puts("1");
        return;
    }
    if (s=="AAAA"||s=="AAAB"||s=="AABA"||s=="AABA"||s=="AABB"||s=="ABAB"||s=="ABBB"||s=="BBAB"||s=="BBBB") return puts("1"),void();
    if (s=="ABAA"||s=="BABA"||s=="BABB"||s=="BBAA") {
        int ans = 1;
        for (int i=1; i<=n-3; ++i) ans = ans*2%mod;
        printf("%d\n", ans);
        return;
    }
    int dp[n+5] = {};
    dp[1] = 0, dp[2] = 1;
    for (int i=3; i<=n; ++i) dp[i] = (dp[i-1]+dp[i-2])%mod;
    printf("%d\n", dp[n]);

}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int c = 0;
    int t;
    if (!c) {
        t = 1;
    }
    else {
        cin >> t;
    }
    while (t--) {
        go();
    }
}