#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#ifdef LOCAL
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) ;
#endif

vector<string> vec_splitter(string s)
{
    s += ',';
    vector<string> res;
    while (!s.empty())
    {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}

void debug_out(
        vector<string> __attribute__ ((unused)) args,
        __attribute__ ((unused)) int idx,
        __attribute__ ((unused)) int LINE_NUM)
{
    cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T)
{
    if (idx > 0)
        cerr << ", ";
    else
        cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss;
    ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}

typedef long long ll;
typedef long double ld;
#define rep(i, start, end) for(int i = start; i < end; ++i)
#define sz(x) (int)((x).size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define clr(d, v) memset(d, v, sizeof(d))
#define pii pair<int, int>
#define X first
#define Y second
//#define debug(x) cerr << #x << " : " << (x) << " "
const long double PI = 3.14159265358979323846;
const long double eps = (1e-15);
//enum
//{
//    LESS, EQUAL, GREATER
//};

//int dcmp(ld x, ld y, ld EPS = eps)
//{
//    if (fabs(x - y) <= EPS)
//        return EQUAL;
//    return x > y ? GREATER : LESS;
//}

const int MOD = 1e9 + 7;
int add(int x, int y)
{
    x += y;
    if (x >= MOD)
        x -= MOD;
    return x;
}

int mult(int x, int y)
{
    return (1LL * x * y)%MOD;
}

int f(int n)
{
    if (n == 0)
        return 1;
    if (n == 1)
        return 2;
    if (n == 2)
        return 3;
    int a = 2, b = 3; // f(1), f(2)
    for (int i = 3; i <= n; ++i)
    {
        int newA = b, newB = add(a, b);
        a = newA;
        b = newB;
    }
    return b;
}

int pwr(int base, int exp)
{
    int ret = 1;
    for (; exp; exp >>= 1, base = mult(base, base))
        if (exp&1)
            ret = mult(ret, base);
    return ret;
}

void myMain()
{
    int n;
    cin >> n;
    int c[2][2];
    rep(i,0,2)
    {
        rep(j, 0, 2)
        {
            char t;
            cin >> t;
            c[i][j] = t - 'A';
        }
    }

    if (n == 2)
    {
        cout << 1;
        return;
    }
    if (c[0][1] == 0)
    {
        if (c[0][0] == 0)
            cout << 1;
        else
        {
            if (c[1][0] == 0)
                cout << f(n - 3);
            else
                cout << pwr(2, n - 3);
        }
    }
    else
    {
        if (c[1][1] == 1)
            cout << 1;
        else
        {
            if (c[1][0] == 1)
                cout << f(n - 3);
            else
                cout << pwr(2, n - 3);
        }
    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    int tc = 1;
//    cin >> tc;
    while(tc--)
        myMain();
}
#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
#include <random>
#include <cassert>
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using namespace std;
#define int long long
#define CONTAINS_VEC(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define REPE(i, n) for (int (i)=0; (i) <= (n); (i)++)
#define CONTAINS_MAP(m, a) ((m).find((a)) != m.end())
#define CONTAINS_SET(m, a) ((m).find((a)) != m.end())
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; exit(0); }
void Yes() { cout << "Yes" << endl; exit(0); }
void No() { cout << "No" << endl; exit(0); }





//---------- 1000000007 ----------
const int MOD = 1000000007;
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; }



signed main()
{
	int N, P;
	cin >> N >> P;

	mint p = P - 2;
	mint a = p.pow(N - 1);
	mint ans = a * (P - 1);
	cout << ans << endl;
}


