#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define per(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
//mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename T>void chkmax(T&x,T y){if(x<y)x=y;}
template<typename T>void chkmin(T&x,T y){if(x>y)x=y;}
inline int read(){
  #define nc getchar()
  bool f=0;int x=0;char c=nc;
  while(c<48)f|=c=='-',c=nc;
  while(c>47)x=x*10+(c^48),c=nc;
  return f?-x:x;
  #undef nc
}

typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

string R(string str){
  string res;
  for(char c:str)res.push_back(c=='A'?'B':'A');
  return res;
}

vector<string>divide(int N){
  vector<string>res;
  if(N==1)return res;
  vector<string>vec=divide(N/2);
  string ini="";
  rep(i,1,N/2)ini+='A';
  rep(i,1,N/2)ini+='B';
  res.push_back(ini);
  for(string str:vec)res.push_back(str+str);
  for(string str:vec)res.push_back(str+R(str));
  return res;
}

void solve(){
  int N;cin>>N;
  auto ans=divide(1<<N);
  printf("%d\n",(int)ans.size());
  for(string str:ans)cout<<str<<endl;
}

signed main(){
//  int T=read();
//  while(T--)solve();
  solve();
  return 0;
}
//g++ -std=c++14 test.cpp -o test.out

#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <map> 
#include <unordered_map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (1LL<<60);
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;

//https://github.com/atcoder-live/library/blob/master/mint.cpp
struct mint {
  LL x; 
  mint(LL x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(LL t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
 
struct combination {
  vector<mint> fact, ifact;//factに階乗を計算、ifactはその各々に対する逆元
  combination(LL n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (LL i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (LL i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(LL n,LL k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};
 
LL N;
char CAA,CAB,CBA,CBB;

mint ans = 1;

mint dp(){
    //dp[i][c]:
    //i文字目までカウント、最後に使った文字がc
    vector<map<char,mint>> dp((N-3)+1);
    dp[0]['A'] = 1;
    dp[0]['B'] = 1;//Bは2文字以上連続しない
    for(int i=0;i<N-3;i++){
        dp[i+1]['A'] = (dp[i]['A'] + dp[i]['B']);
        dp[i+1]['B'] = dp[i]['A'];
    }
    return dp[N-3]['A'];
}
void solve(){
    if(N<=3) return;
    if(CAB=='A'){
        if(CAA=='A') return;
        if(CAA=='B'){
            if(CBA=='A'){
                ans = dp();
                return;
            }
            if(CBA=='B'){
                ans = mint(2).pow(N-3);
                return;
            }
        }
    }
    if(CAB=='B'){
        if(CBB=='B') return;
        if(CBB=='A'){
            if(CBA=='B'){
                ans = dp();
                return;
            }
            if(CBA=='A'){
                ans = mint(2).pow(N-3);
                return;
            }
        }
    }
}
 
int main(){
    cin >> N;
    cin >> CAA >> CAB >> CBA >> CBB;
 
    solve();
 
    cout << ans.x << endl;
    return 0;
}