// #include #include #include #include #include using namespace std; typedef long long ll; typedef long double ld; typedef pair PP; // #define MOD 1000000007 #define MOD 998244353 #define INF 2305843009213693951ll #define PI 3.141592653589 #define setdouble setprecision #define REP(i,n) for(ll i=0;i<(n);++i) #define OREP(i,n) for(ll i=1;i<=(n);++i) #define RREP(i,n) for(ll i=(n)-1;i>=0;--i) #define ORREP(i,n) for(ll i=(n);i>=1;--i) #define rep(i,a,b) for(ll i=(a);i<=(b);++i) #define ALL(v) (v).begin(), (v).end() #define chmin(k,m) k = min(k,m) #define chmax(k,m) k = max(k,m) #define GOODBYE do { cout << "-1" << endl; return 0; } while (false) #define MM <<" "<< #define Endl endl int main(void){ cin.tie(nullptr); ios::sync_with_stdio(false); ll N,K; cin >> N >> K; if(0){ ll c = 0; for(ll j=0;j<(1<>i)%2==1){ S[N-i-1] = 'M'; }else{ S[N-i-1] = 'A'; } } bool ok = false; REP(i,N-2){ if(S[i]=='M' && S[i+1]=='M' && S[i+2]=='A'){ ok = true; } } if(ok){ c++; cout << c MM S << endl; } } cout << c << endl; } // dp[i][j] := i 文字見たときに、先頭の 3 文字が j のとき候補の個数 // ただし 10^7 以上は管理しない vector> dp(N+1,vector(8,0)); dp[3][6] = 1; ll R = 2; for(ll i=4;i<=N;i++){ REP(k,8){ if(k==6)continue; ll y = k;if(y>=4)y-=4;y*=2; dp[i][k] = dp[i-1][y] + dp[i-1][y+1]; } dp[i][6] += R; R = min(2*R,10'000'000ll); REP(k,8){ chmin(dp[i][k],10'000'000ll); } } // vector dpsum(N+1,0); // REP(k,8){ // REP(j,3){cout << ((k>>(2-j))%2==1?'M':'A');}cout << " "; // RREP(i,N+1){ // cout << dp[i][k] << " "; // dpsum[i] += dp[i][k]; // chmin(dpsum[i],10'000'000ll); // } // cout << endl; // } // cout << "!!! "; // RREP(i,N+1){ // cout << dpsum[i] << " "; // }cout << endl; // dp2[i][j] := i 文字見たときに、先頭の 1 文字が j のとき候補の個数 // ただし 10^7 以上は管理しない // vector> dp2(N+1,vector(2,0)); // REP(i,N+1){ // REP(k,8){ // dp2[i][k>=4] += dp[i][k]; // } // REP(k,2){ // chmin(dp2[i][k],10'000'000ll); // } // } // REP(k,2){ // cout << "AM"[k] << " "; // RREP(i,N+1){ // cout << dp2[i][k] << " "; // } // cout << endl; // } // cout << "! "; // RREP(i,N+1){ // cout << dp2[i][0]+dp2[i][1] << " "; // }cout << endl; string Ans(N,'-'); ll M = K-1; // 最初の 3 文字を決める ll c = 0; ll prev; REP(k,8){ // cout << "? " << k MM c MM dp[N][k] MM M << endl; if(M < c + dp[N][k]){ REP(j,3){ Ans[j] = ((k>>(2-j))%2==1?'M':'A'); } M -= c; prev = k; if(prev>=4){prev-=4;} break; }else{ c += dp[N][k]; } } for(ll i=3;i<=N;i++){ // cout << i MM prev MM dp[N-(i-2)][2*prev] MM M << endl; if(Ans[i-3]=='M' && Ans[i-2]=='M' && Ans[i-1]=='A'){ ll m = M; for(ll j=N-1;j>=i;j--){ Ans[j] = 'A'; if((m%2)==1){Ans[j] = 'M';} m /= 2; } break; } if(M < dp[N-(i-2)][2*prev]){ Ans[i] = 'A'; }else{ Ans[i] = 'M'; M -= dp[N-(i-2)][2*prev]; } prev = 0; if(Ans[i-1]=='M')prev+=2; if(Ans[i]=='M')prev+=1; // cout << Ans << endl; } cout << Ans << endl; // ll M = K-1; // REP(i,N){ // cout << "! " << N-i MM M << endl; // cout << "? " << dp2[N-i][0] MM dp2[N-i][1] << endl; // if(M < dp2[N-i][0]){ // Ans[i] = 'A'; // }else{ // Ans[i] = 'M'; // M -= dp2[N-i][0]; // } // } // cout << Ans << endl; return 0; }