#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define MD (998244353U)
#define MINT_W (32U)
#define MINT_R (301989884U)
#define MINT_RR (932051910U)
#define MINT_MDNINV (998244351U)
#define MD_PRIMITIVE_ROOT (3U)
#define PI 3.14159265358979323846
void*wmem;
char memarr[96000000];
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
(*arr)=(T*)(*mem);
(*mem)=((*arr)+x);
}
template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
walloc1d(arr, x2-x1, mem);
(*arr) -= x1;
}
struct Mint{
unsigned val;
Mint(){
val=0;
}
Mint(int a){
val = mulR(a);
}
Mint(unsigned a){
val = mulR(a);
}
Mint(long long a){
val = mulR(a);
}
Mint(unsigned long long a){
val = mulR(a);
}
inline unsigned mulR(unsigned a){
return (unsigned long long)a*MINT_R%MD;
}
inline unsigned mulR(int a){
if(a < 0){
a = a%((int)MD)+(int)MD;
}
return mulR((unsigned)a);
}
inline unsigned mulR(unsigned long long a){
return mulR((unsigned)(a%MD));
}
inline unsigned mulR(long long a){
a %= (int)MD;
if(a < 0){
a += MD;
}
return mulR((unsigned)a);
}
inline unsigned reduce(unsigned T){
unsigned m = T * MINT_MDNINV;
unsigned t = (unsigned)((T + (unsigned long long)m*MD) >> MINT_W);
if(t >= MD){
t -= MD;
}
return t;
}
inline unsigned reduce(unsigned long long T){
unsigned m = (unsigned)T * MINT_MDNINV;
unsigned t = (unsigned)((T + (unsigned long long)m*MD) >> MINT_W);
if(t >= MD){
t -= MD;
}
return t;
}
inline unsigned get(){
return reduce(val);
}
inline Mint &operator+=(Mint a){
val += a.val;
if(val >= MD){
val -= MD;
}
return *this;
}
inline Mint &operator-=(Mint a){
if(val < a.val){
val = val + MD - a.val;
}
else{
val -= a.val;
}
return *this;
}
inline Mint &operator*=(Mint a){
val = reduce((unsigned long long)val*a.val);
return *this;
}
inline Mint &operator/=(Mint a){
return *this *= a.inverse();
}
inline Mint operator+(Mint a){
return Mint(*this)+=a;
}
inline Mint operator-(Mint a){
return Mint(*this)-=a;
}
inline Mint operator*(Mint a){
return Mint(*this)*=a;
}
inline Mint operator/(Mint a){
return Mint(*this)/=a;
}
inline Mint operator+(int a){
return Mint(*this)+=Mint(a);
}
inline Mint operator-(int a){
return Mint(*this)-=Mint(a);
}
inline Mint operator*(int a){
return Mint(*this)*=Mint(a);
}
inline Mint operator/(int a){
return Mint(*this)/=Mint(a);
}
inline Mint operator+(long long a){
return Mint(*this)+=Mint(a);
}
inline Mint operator-(long long a){
return Mint(*this)-=Mint(a);
}
inline Mint operator*(long long a){
return Mint(*this)*=Mint(a);
}
inline Mint operator/(long long a){
return Mint(*this)/=Mint(a);
}
inline Mint operator-(void){
Mint res;
if(val){
res.val=MD-val;
}
else{
res.val=0;
}
return res;
}
inline operator bool(void){
return val!=0;
}
inline operator int(void){
return get();
}
inline operator long long(void){
return get();
}
inline Mint inverse(){
int a = val;
int b = MD;
int u = 1;
int v = 0;
int t;
Mint res;
while(b){
t = a / b;
a -= t * b;
swap(a, b);
u -= t * v;
swap(u, v);
}
if(u < 0){
u += MD;
}
res.val = (unsigned long long)u*MINT_RR % MD;
return res;
}
inline Mint pw(unsigned long long b){
Mint a(*this);
Mint res;
res.val = MINT_R;
while(b){
if(b&1){
res *= a;
}
b >>= 1;
a *= a;
}
return res;
}
inline bool operator==(int a){
return mulR(a)==val;
}
inline bool operator!=(int a){
return mulR(a)!=val;
}
}
;
inline Mint operator+(int a, Mint b){
return Mint(a)+=b;
}
inline Mint operator-(int a, Mint b){
return Mint(a)-=b;
}
inline Mint operator*(int a, Mint b){
return Mint(a)*=b;
}
inline Mint operator/(int a, Mint b){
return Mint(a)/=b;
}
inline Mint operator+(long long a, Mint b){
return Mint(a)+=b;
}
inline Mint operator-(long long a, Mint b){
return Mint(a)-=b;
}
inline Mint operator*(long long a, Mint b){
return Mint(a)*=b;
}
inline Mint operator/(long long a, Mint b){
return Mint(a)/=b;
}
inline int my_getchar_unlocked(){
static char buf[1048576];
static int s = 1048576;
static int e = 1048576;
if(s == e && e == 1048576){
e = fread_unlocked(buf, 1, 1048576, stdin);
s = 0;
}
if(s == e){
return EOF;
}
return buf[s++];
}
inline void rd(int &x){
int k;
int m=0;
x=0;
for(;;){
k = my_getchar_unlocked();
if(k=='-'){
m=1;
break;
}
if('0'<=k&&k<='9'){
x=k-'0';
break;
}
}
for(;;){
k = my_getchar_unlocked();
if(k<'0'||k>'9'){
break;
}
x=x*10+k-'0';
}
if(m){
x=-x;
}
}
inline void rd(char &c){
int i;
for(;;){
i = my_getchar_unlocked();
if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
break;
}
}
c = i;
}
inline int rd(char c[]){
int i;
int sz = 0;
for(;;){
i = my_getchar_unlocked();
if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
break;
}
}
c[sz++] = i;
for(;;){
i = my_getchar_unlocked();
if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
break;
}
c[sz++] = i;
}
c[sz]='\0';
return sz;
}
struct MY_WRITER{
char buf[1048576];
int s;
int e;
MY_WRITER(){
s = 0;
e = 1048576;
}
~MY_WRITER(){
if(s){
fwrite_unlocked(buf, 1, s, stdout);
}
}
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
MY_WRITER_VAR.s = 0;
}
MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
my_putchar_unlocked(a);
}
inline void wt_L(int x){
int s=0;
int m=0;
char f[10];
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
my_putchar_unlocked('-');
}
while(s--){
my_putchar_unlocked(f[s]+'0');
}
}
inline void wt_L(Mint x){
int i;
i = (int)x;
wt_L(i);
}
template<class T, class S> inline T pow_L(T a, S b){
T res = 1;
res = 1;
for(;;){
if(b&1){
res *= a;
}
b >>= 1;
if(b==0){
break;
}
a *= a;
}
return res;
}
inline double pow_L(double a, double b){
return pow(a,b);
}
struct fft_pnt{
double x;
double y;
fft_pnt(void){
}
fft_pnt(double a, double b){
x = a;
y = b;
}
void set(double a, double b){
x = a;
y = b;
}
fft_pnt& operator+=(fft_pnt a){
x+=a.x;
y+=a.y;
return *this;
}
fft_pnt& operator-=(fft_pnt a){
x-=a.x;
y-=a.y;
return *this;
}
fft_pnt& operator*=(fft_pnt a){
fft_pnt p = *this;
x = p.x*a.x-p.y*a.y;
y = p.x*a.y+p.y*a.x;
return *this;
}
fft_pnt operator+(fft_pnt a){
return fft_pnt(*this) += a;
}
fft_pnt operator-(fft_pnt a){
return fft_pnt(*this) -= a;
}
fft_pnt operator*(fft_pnt a){
return fft_pnt(*this) *= a;
}
}
;
void fft(int n, fft_pnt x[], void *mem = wmem){
int i;
int j;
int n1;
int n2;
int n3;
int step = 1;
double theta = 2*PI / n;
double tmp;
fft_pnt w1;
fft_pnt w2;
fft_pnt w3;
fft_pnt a;
fft_pnt b;
fft_pnt c;
fft_pnt d;
fft_pnt aa;
fft_pnt bb;
fft_pnt cc;
fft_pnt dd;
fft_pnt*y = (fft_pnt*)mem;
while(n > 2){
n1 = n / 4;
n2 = n1 + n1;
n3 = n1 + n2;
for(i=(0);i<(n1);i++){
w1 = fft_pnt(cos(i*theta),-sin(i*theta));
w2 = w1*w1;
w3 = w1*w2;
for(j=(0);j<(step);j++){
a = x[j+step*i];
b = x[j+step*(i+n1)];
c = x[j+step*(i+n2)];
d = x[j+step*(i+n3)];
aa = a + c;
bb = a - c;
cc = b + d;
dd = b - d;
tmp = dd.y;
dd.y = dd.x;
dd.x = -tmp;
y[j+step*(4*i )] = aa + cc;
y[j+step*(4*i+1)] = w1*(bb - dd);
y[j+step*(4*i+2)] = w2*(aa - cc);
y[j+step*(4*i+3)] = w3*(bb + dd);
}
}
n /= 4;
step *= 4;
theta *= 4;
swap(x,y);
}
if(n==2){
for(i=(0);i<(step);i++){
y[i] = x[i] + x[i+step];
y[i+step] = x[i] - x[i+step];
}
n /= 2;
step *= 2;
theta *= 2;
swap(x,y);
}
for(i=(0);i<(step);i++){
y[i] = x[i];
}
}
void fftinv(int n, fft_pnt x[], void *mem = wmem){
int i;
int j;
int n1;
int n2;
int n3;
int step = 1;
double theta = 2*PI / n;
double tmp;
fft_pnt w1;
fft_pnt w2;
fft_pnt w3;
fft_pnt a;
fft_pnt b;
fft_pnt c;
fft_pnt d;
fft_pnt aa;
fft_pnt bb;
fft_pnt cc;
fft_pnt dd;
fft_pnt*y = (fft_pnt*)mem;
while(n > 2){
n1 = n / 4;
n2 = n1 + n1;
n3 = n1 + n2;
for(i=(0);i<(n1);i++){
w1 = fft_pnt(cos(i*theta),sin(i*theta));
w2 = w1*w1;
w3 = w1*w2;
for(j=(0);j<(step);j++){
a = x[j+step*i];
b = x[j+step*(i+n1)];
c = x[j+step*(i+n2)];
d = x[j+step*(i+n3)];
aa = a + c;
bb = a - c;
cc = b + d;
dd = b - d;
tmp = dd.y;
dd.y = dd.x;
dd.x = -tmp;
y[j+step*(4*i )] = aa + cc;
y[j+step*(4*i+1)] = w1*(bb + dd);
y[j+step*(4*i+2)] = w2*(aa - cc);
y[j+step*(4*i+3)] = w3*(bb - dd);
}
}
n /= 4;
step *= 4;
theta *= 4;
swap(x,y);
}
if(n==2){
for(i=(0);i<(step);i++){
y[i] = x[i] + x[i+step];
y[i+step] = x[i] - x[i+step];
}
n /= 2;
step *= 2;
theta *= 2;
swap(x,y);
}
for(i=(0);i<(step);i++){
y[i] = x[i];
}
}
void fft(int n, Mint x[], Mint root = MD_PRIMITIVE_ROOT, void *mem = wmem){
int i;
int j;
int n1;
int n2;
int n3;
int step = 1;
Mint w1;
Mint w2;
Mint w3;
Mint a;
Mint b;
Mint c;
Mint d;
Mint aa;
Mint bb;
Mint cc;
Mint dd;
Mint tmp;
Mint*y;
walloc1d(&y, n, &mem);
tmp = root.pw((MD-1)/4*3);
root = root.pw((MD-1)/n);
while(n > 2){
n1 = n / 4;
n2 = n1 + n1;
n3 = n1 + n2;
w1.val = MINT_R;
for(i=(0);i<(n1);i++){
w2 = w1*w1;
w3 = w1*w2;
for(j=(0);j<(step);j++){
a = x[j+step*i];
b = x[j+step*(i+n1)];
c = x[j+step*(i+n2)];
d = x[j+step*(i+n3)];
aa = a + c;
bb = a - c;
cc = b + d;
dd = (b - d) * tmp;
y[j+step*(4*i )] = aa + cc;
y[j+step*(4*i+1)] = w1*(bb - dd);
y[j+step*(4*i+2)] = w2*(aa - cc);
y[j+step*(4*i+3)] = w3*(bb + dd);
}
w1 *= root;
}
n /= 4;
step *= 4;
root *= root;
root *= root;
swap(x,y);
}
if(n==2){
for(i=(0);i<(step);i++){
y[i] = x[i] + x[i+step];
y[i+step] = x[i] - x[i+step];
}
n /= 2;
step *= 2;
root *= root;
swap(x,y);
}
for(i=(0);i<(step);i++){
y[i] = x[i];
}
}
void fftinv(int n, Mint x[], Mint root = MD_PRIMITIVE_ROOT, void *mem = wmem){
int i;
int j;
int n1;
int n2;
int n3;
int step = 1;
Mint w1;
Mint w2;
Mint w3;
Mint a;
Mint b;
Mint c;
Mint d;
Mint aa;
Mint bb;
Mint cc;
Mint dd;
Mint tmp;
Mint*y;
walloc1d(&y, n, &mem);
root = root.inverse();
tmp = root.pw((MD-1)/4);
root = root.pw((MD-1)/n);
while(n > 2){
n1 = n / 4;
n2 = n1 + n1;
n3 = n1 + n2;
w1.val = MINT_R;
for(i=(0);i<(n1);i++){
w2 = w1*w1;
w3 = w1*w2;
for(j=(0);j<(step);j++){
a = x[j+step*i];
b = x[j+step*(i+n1)];
c = x[j+step*(i+n2)];
d = x[j+step*(i+n3)];
aa = a + c;
bb = a - c;
cc = b + d;
dd = (b - d) * tmp;
y[j+step*(4*i )] = aa + cc;
y[j+step*(4*i+1)] = w1*(bb + dd);
y[j+step*(4*i+2)] = w2*(aa - cc);
y[j+step*(4*i+3)] = w3*(bb - dd);
}
w1 *= root;
}
n /= 4;
step *= 4;
root *= root;
root *= root;
swap(x,y);
}
if(n==2){
for(i=(0);i<(step);i++){
y[i] = x[i] + x[i+step];
y[i+step] = x[i] - x[i+step];
}
n /= 2;
step *= 2;
root *= root;
swap(x,y);
}
for(i=(0);i<(step);i++){
y[i] = x[i];
}
}
int N;
int M;
int T;
int K;
char F[100000+2];
char S[100000+2];
int bc;
int sc;
int trial;
int big[100000];
int small[100000];
Mint arr1[7][270000];
Mint arr2[7][270000];
Mint arr[270000];
int main(){
int c, i, r;
wmem = memarr;
Mint res = 0;
Mint v;
rd(N);
rd(M);
rd(T);
rd(K);
rd(F);
rd(S);
for(i=(0);i<(N);i++){
F[i] -= 'A';
}
for(i=(0);i<(K);i++){
S[i] -= 'A';
}
trial = N - K + 1;
sc = M / T;
bc = sc + 1;
for(i=(0);i<(N);i++){
arr1[F[i]][i] = 1;
}
for(i=(0);i<(K);i++){
arr2[S[K-1-i]][i] = 1;
}
for(c=(0);c<(T);c++){
fft(1<<18, arr1[c]);
}
for(c=(0);c<(T);c++){
fft(1<<18, arr2[c]);
}
int tU__gIr_ = M%T;
for(r=(0);r<(tU__gIr_);r++){
for(c=(0);c<(T);c++){
for(i=(0);i<(1<<18);i++){
arr[i] += arr1[c][i] * arr2[(c+r)%T][i];
}
}
}
fftinv(1<<18, arr);
v = 1 / Mint(1<<18);
for(i=(0);i<(trial);i++){
big[i] = (int)(arr[K-1+i] * v);
}
for(i=(0);i<(trial);i++){
small[i] = K - big[i];
}
for(i=(0);i<(trial);i++){
res += ((pow_L(Mint(sc),small[i]))) * ((pow_L(Mint(bc),big[i])));
}
wt_L(res);
wt_L('\n');
return 0;
}
// cLay version 20201227-1
// --- original code ---
// #define MD 998244353
// int N, M, T, K;
// char F[1d5+2], S[1d5+2];
//
// int bc, sc, trial;
// int big[1d5], small[1d5];
// Mint arr1[7][2.7d5], arr2[7][2.7d5], arr[2.7d5];
// {
// Mint res = 0, v;
// rd(N,M,T,K,F,S);
// rep(i,N) F[i] -= 'A';
// rep(i,K) S[i] -= 'A';
//
// trial = N - K + 1;
// sc = M / T;
// bc = sc + 1;
//
// rep(i,N) arr1[F[i]][i] = 1;
// rep(i,K) arr2[S[K-1-i]][i] = 1;
// rep(c,T) fft(1<<18, arr1[c]);
// rep(c,T) fft(1<<18, arr2[c]);
// REP(r,M%T) rep(c,T) rep(i,1<<18) arr[i] += arr1[c][i] * arr2[(c+r)%T][i];
//
// fftinv(1<<18, arr);
// v = 1 / Mint(1<<18);
// rep(i,trial) big[i] = (int)(arr[K-1+i] * v);
// rep(i,trial) small[i] = K - big[i];
// rep(i,trial) res += (Mint(sc) ** small[i]) * (Mint(bc) ** big[i]);
// wt(res);
// }