#ifdef __LOCAL
  #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b) {if(a<b) {a=b; return true;} return false;}
template<typename T> bool chmin(T &a,T b) {if(a>b) {a=b; return true;} return false;}
#define itn int
#define fi first
#define se second
#define intmax numeric_limits<int>::max()
#define llmax numeric_limits<ll>::max()
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(int)(n);i>=1;i--)
#define all(vec) vec.begin(),vec.end()
#define sortt(vec) sort((vec).begin(),(vec).end())
#define rsort(vec) sort((vec).rbegin(), (vec).rend())
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;
const ll lnf=1ll<<60;

ll rui(ll a,ll n){
  ll ans=1;
  while(n>0){
    if(n&1) ans=ans*a%mod;
    a=a*a%mod;
    n/=2;
  }
  return ans;
}

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  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 { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= 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 { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

mint dp[1010];

int main(){
  dp[1]=2;
  dp[2]=3;
  rep1(i,1e3) dp[i+2]=dp[i+1]+dp[i];
  int n; cin >> n;
  char a,b,c,d; cin >> a >> b >> c >> d;
  if(n==2||n==3){
    cout << 1 << endl;
    return 0;
  }
  if(b=='B'){
    if(d=='B'){
      cout << 1 << endl;
    }
    else{
      if(c=='A'){
        cout << rui(2,n-3) << endl;
      }
      else{
        cout << dp[n-3] << endl;
      }
    }
  }
  else{
    if(a=='A'){
      cout << 1 << endl;
    }
    else{
      if(c=='B'){
        cout << rui(2,n-3) << endl;
      }
      else{
        cout << dp[n-3] << endl;
      }
    }
  }
  
}
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string(string(s)); }
string to_string(bool b) { return to_string(int(b)); }
string to_string(vector<bool>::reference b) { return to_string(int(b)); }
string to_string(char b) { return "'" + string(1, b) + "'"; }
template <typename A, typename B>
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A>
string to_string(A v) {
	string res = "{";
	for (const auto& x : v) res += (res == "{" ? "" : ", ") + to_string(x);
	return res + "}";
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug(T...);
}
#define db(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define db(...) 42
#endif
typedef long long ll;
typedef long double ld;
const int MAXN = 100005;
int val[MAXN];
vector<pair<int, int>> E[MAXN];
int n;
void go(int x) {
	for (auto& e : E[x]) {
		int y = e.first, c = e.second;
		if (val[y]) continue;
		if (c == val[x]) val[y] = (c == n ? 1 : c + 1);
		else val[y] = c;
		go(y);
	}
}
int main() {
	int m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
		int u, v, c;
		scanf("%d%d%d", &u, &v, &c);
		E[u].push_back({v, c});
		E[v].push_back({u, c});
	}
	val[1] = 1;
	go(1);
	for (int i = 1; i <= n; ++i) printf("%d\n", val[i]);
}
