Debate Subsequence Counting

Saint Mary, an ENTP debater, emphasizes her viewpoint repeatedly during a debate. Her argument is represented by a string \(S\), and to stress her point she repeats it \(k\) times (i.e., her speech is the concatenation of \(k\) copies of \(S\)). As her opponent, you only catch a keyword represented by the string \(T\). Your task is to determine the number of subsequences (not necessarily contiguous) within her full speech that are equal to \(T\), and then report the answer modulo \(998244353\).

Formal Problem Statement:

Given a positive integer \(k\) and two strings \(S\) and \(T\). Let \(s\) be the string obtained by concatenating \(S\) with itself \(k\) times, i.e., \(s = S S \dots S\) (\(k\) times). Let \(n = |s|\) and \(m = |T|\). Define the set \[ P = \{ (i_0,i_1,\dots,i_{m-1}) \mid 0 \le i_0 < i_1 < \dots < i_{m-1} < n,\; s_{i_j} = T_j \text{ for all } 0 \le j < m \}, \] and compute \(|P| \bmod 998244353\).

inputFormat

The input consists of three lines:
1. The first line contains a positive integer \(k\).
2. The second line contains the string \(S\).
3. The third line contains the string \(T\).

outputFormat

Output a single integer: the number of subsequences of the repeated string \(s\) that equal \(T\), taken modulo \(998244353\).

sample

1
ab
ab

1