#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	bool flag=1;
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
			flag=0;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return (flag?x:~(x-1));
}
int n,m,k,ans,a[200002],b[200002];
const int mod=998244353;
int qp(int x,int y)
{
	if(y==0)
		return 1;
	if(y==1)
		return x;
	if(x<=1)
		return x;
	int ans=qp(x,y/2);
	ans=(ans*ans)%mod;
	if(y&1)
		ans=(ans*x)%mod;
	return ans;
}
signed main()
{
	n=read();
	m=read();
	k=read();
	for(int i=1;i<=k;i++)
//		b[k-i+1]=b[k-i+2]+qp(i,m)-qp(i-1,m);
		b[k-i+1]=qp(i,m);
	if(n==1&&m==1)
	{
		cout<<k;
		return 0;
	}
	if(n==1)
	{
		cout<<qp(k,m)<<endl;
		return 0;
	}
	if(m==1)
	{
		cout<<qp(k,n)<<endl;
		return 0;
	}
	for(int i=1;i<=k;i++)
		ans=(ans+(qp(i,n)-qp(i-1,n)+mod)%mod*b[i]%mod)%mod;
	cout<<ans<<endl;
	return 0;
}

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

#define M 1005
#define LL long long
const LL mod = 1000000007;

int n;
LL f[M];
char Caa, Cab, Cba, Cbb;

inline LL qkpow (LL x, LL y){
	LL res = 1;
	while (y){
		if (y & 1)
			res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
signed main (){
	scanf ("%d\n%c\n%c\n%c\n%c", &n, &Caa, &Cab, &Cba, &Cbb);
	if (n == 3 || n == 2){
		printf ("1\n");
		return 0;
	}
	f[1] = 2, f[2] = 3;
	for (int i = 3; i <= n; i ++)
		f[i] = (f[i - 1] + f[i - 2]) % mod;
	if (Cab == 'B'){
		if (Cbb == 'B')
			printf ("1\n");
		else{
			if (Cba == 'A'){
				printf ("%lld\n", qkpow (2, n - 3));
			}
			else{
				printf ("%lld\n", f[n - 3]);
			}
		}
	}
	else{
		if (Caa == 'A')
			printf ("1\n");
		else{
			if (Cba == 'B'){
				printf ("%lld\n", qkpow (2, n - 3));
			}
			else{
				printf ("%lld\n", f[n - 3]);
			}
		}
	}
	return 0;
}