题目背景

因其很有实力被尊称为圣母。

圣母好闪，拜谢圣母！

题目描述

圣母是一名辩论家，即 ENTP。

她在进行一次辩论时的观点是字符串 $S$，她为了让对方信服她的观点她会强调 $k$ 次，所以她的辩词即为 $k$ 个字符串 $S$ 依次首尾相接。

你作为反驳的人可能不能听清楚她说的所有话，所以你只能抓取关键词 $T$，你需要求出 $k$ 个首尾相接的 $S$ 中有多少个子序列（不一定连续）为 $T$，答案对 $998244353$ 取模。

---

【形式化题意】

给定一个正整数 $k$ 和两个字符串 $S,T$。

设字符串 $s$ 为 $k$ 个字符串 $S$ 首尾相接得到的字符串，$n=\vert s \vert , m=\vert T \vert$。

设答案集合 $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 \}$，请求出 $\vert P \vert \bmod 998244353$。

输入格式

输入共 $3$ 行。

第 $1$ 行 $1$ 个整数，表示 $k$。

第 $2$ 行 $1$ 个字符串，表示 $S$。

第 $3$ 行 $1$ 个字符串，表示 $T$。

输出格式

输出共 $1$ 行 $1$ 个整数，表示答案。

2
stocyhorz
cyh

4

4
c
ccc

4

提示

【样例 1 解释】

将 $S$ 重复 $2$ 次得到 $\texttt{stocyhorzstocyhorz}$。

答案集合 $P=\{(3,4,5),(3,4,14),(3,13,14),(12,13,14) \}$，因此 $\vert P\vert=4$。

---

【数据范围】

对于 $100\%$ 的数据，$0<k\le10^{18}$，$0 < \vert S \vert \le 5 \times 10^3$，$0 < \vert T \vert \le 10$，字符串 $S,T$ 均由小写英文字母组成。

$\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}$