U612392 追忆

我常常追忆过去。 生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。 云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。 追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。 过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。 我该在哪里停留？我问我自己。

出题入没有灵感了，所以这个题只有简化题意。 给定整数 $k$ 和字符串 $S$，求长度为 $k+ \left | S \right |$ 且仅由小写字母构成的字符串中子串包含 $S$ 的字符串个数，答案对 $998244353$ 取模。 子串可以不连续。 $k，\left | S \right | \le 10^6$。

第一行一个正整数 $k$。 第二行一个字符串 $S$。

输出一行表示答案。

对于 $30 \%$ 的数据，$k+\left | S \right | \le 5$。 对于 $100 \%$ 的数据，$k \le 10^6$，$\left | S \right | \le 10^6$。