#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll> pql;
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, k, n) for(ll i = ll(k); i <= ll(n); i++)
#define rep3(i, n, k) for(ll i = ll(n); i >= ll(k); i--)
#define all(v) (v).begin(), (v).end()
ll mod(ll a, ll b) {if(b == 0) return 0; return (a % b + b) % b;}
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 2e5;
const ld eps = 1e-9;
const char newl = '\n';

ll modpow(ll n) {
  if(n==0) return 1;
  else if(n%2==0) return modpow(n/2)*modpow(n/2)%MOD;
  else return 2*modpow(n-1)%MOD;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll n;
  char caa, cab, cba, cbb;
  cin >> n >> caa >> cab >> cba >> cbb;

  if(n==2) cout << 1;

  else if((caa=='A' && cab=='A') || (cab=='B' && cbb=='B')) {
    cout << 1;
  }

  else if((cab=='B' && cba=='A' && cbb=='A') || (caa=='B' && cab=='A' && cba=='B')) {
    cout << modpow(n-3);
  }

  else if((cab=='B' && cba=='B' && cbb=='A') || (caa=='B' && cab=='A' && cba=='A')) {
    vvl bc(n-1, vl(n-1));
    rep(i, n-1) {
      bc[i][0] = 1;
      bc[i][i] = 1;
    }
    rep(i, n-1) rep2(j, 1, i-1) bc[i][j] = (bc[i-1][j-1] + bc[i-1][j]) % MOD;
    ll ans = 0;
    rep(k, n/2) (ans += bc[n-2-k][k]) %= MOD;
    cout << ans;
  }

  else return -1;

  cout << newl;
  return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
int max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int min(int a,int b)
{
	if(a<b)
		return a;
	return b;
}
signed main() {
 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 

 string s;
 cin>>s;
 map<int,int> mp;
 int x=0;
 for(auto i:s){
 	mp[(i-'0')%3]++;
 	x+=(i-'0');
 }
 x%=3;
 int ans=s.size();
 if(x==1)
 {
 	if(mp[1]>=1)
 	ans=min(ans,1);
  	if(mp[2]>=2)
  		ans=min(ans,2);
 }
 else if(x==2)
 {
 	if(mp[1]>=2)
 	ans=min(ans,2);
 	if(mp[2]>=1)
 	ans=min(ans,1);
 }
 else
 	ans=0;
 if(ans==s.size())
 	ans=-1;

 cout<<ans;
}
