Background

is respectfully called “Shengmu” (shèng mǔ) because of their strong abilities.

Shengmu is so dazzling. Thanks to Shengmu!

Problem Description

Shengmu is a debater, i.e. an ENTP.

In one debate, her viewpoint is the string $S$. To convince the other side, she will emphasize it $k$ times, so her speech is the concatenation of $k$ copies of the string $S$ in order.

As the rebutter, you may not be able to hear everything clearly, so you can only catch the keyword $T$. You need to find, in the string formed by concatenating $k$ copies of $S$, how many subsequences (not necessarily contiguous) are equal to $T$. Output the answer modulo $998244353$.

---

[Formal statement]

Given a positive integer $k$ and two strings $S, T$.

Let the string $s$ be the string obtained by concatenating $k$ copies of $S$. Let $n=\vert s \vert$ and $m=\vert T \vert$.

Let the answer set be $P=\{ (i_0,i_1,\dots,i_{m-1}) \mid 0\le i_0 < i_1 < \dots < i_{m-1} < n, \forall~0 \le j < m, s_{i_j}=T_j \}$. Compute $\vert P \vert \bmod 998244353$.

Input Format

There are $3$ lines of input.

Line $1$ contains one integer $k$.

Line $2$ contains one string $S$.

Line $3$ contains one string $T$.

Output Format

Output one line containing one integer, the answer.

2
stocyhorz
cyh

4

4
c
ccc

4

Hint

[Explanation for Sample 1]

Repeat $S$ $2$ times to get $\texttt{stocyhorzstocyhorz}$.

The answer set is $P=\{(3,4,5),(3,4,14),(3,13,14),(12,13,14) \}$, so $\vert P\vert=4$.

---

[Constraints]

For all testdata, $0<k\le10^{18}$, $0 < \vert S \vert \le 5 \times 10^3$, $0 < \vert T \vert \le 10$. Both strings $S$ and $T$ consist of lowercase English letters.

$\text{Point}$	$k\le$	$\vert S\vert\le$	$\vert T\vert\le$
$1\sim2$	$10^{18}$	$5 \times 10^3$	$1$
$3$	$1$		$2$
$4\sim5$	$100$	$5 \times 10 ^3$
$6\sim7$	$1$	$50$	$4$
$8\sim10$	$10$	$5 \times 10^3$	$10$
$11\sim20$	$10^{18}$

Translated by ChatGPT 5