T3 选取字符串

题目信息

时间限制: 1s

空间限制: 512M

输入文件: string.in

输出文件: string.out

题目描述

小明有一个长为 $n$ 的字符串 $S$，下标从 $1$ 到 $n$。

用 $S_i$ 表示第 $1$ 到 $i$ 个字符组成的前缀，$S_0$ 表示空串，即长为 $0$ 的前缀。现在要在 $\{S_0,S_1,\dots , S_n\}$ 这些串中任选 $k$ 个不同的串 $S_{t_1}, S_{t_2}, \dots , S_{t_k}$，再依次选出两个字符串 $p,q$（可以为空串，可以相等），要求对于每个 $j=1,2,\dots , k$，$p, q$ 都既是 $S_{t_i}$ 的前缀也是其后缀。空串是任何串的前缀和后缀。

求选取 $(\{S_{t_i}\},p,q)$ 的总共方案数。两个方案不同当且仅当某个 $S_i$ 仅在其中一个方案中被选，或者二者中的 $p,q$ 有至少一个不同。方案数对 $998244353$ 取模。

输入格式

第一行一个正整数 $k$。

第二行一个非空字符串 $S$，仅包含小写字母。

输出格式

输出一行一个非负整数表示方案数模 $998244353$ 的值。

样例

样例输入 1

2
abaab

样例输出 1

27

样例解释 1

• $\{a, aba\}$ 的 $p,q$ 分别都可以是空串或 $a$，共 $4$ 种方案；
• $\{a, abaa\}$ 的 $p,q$ 分别都可以是空串或 $a$，共 $4$ 种方案；
• $\{ab, abaab\}$ 的 $p,q$ 分别都可以是空串或 $ab$，共 $4$ 种方案；
• $\{aba, abaa\}$ 的 $p,q$ 分别都可以是空串或 $a$，共 $4$ 种方案；
• 剩余的 $11$ 个字符串集合对应的 $p,q$ 只能是空串，共 $11$ 种方案；

总计 $27$ 种方案。

样例输入 2

19
qwqfqwqwwwwqwffqwwqwwqfqwwqfwqwq

样例输出 2

818809200

数据范围与提示

对于所有数据，$1\le n, k \le 10^6$。

对于 $20\%$ 的数据，$n\le 20$；

对于 $40\%$ 的数据，$n\le 200$；

对于 $60\%$ 的数据，$n\le 2000$；

对于 $80\%$ 的数据，$n\le 10^5$；

对于 $100\%$ 的数据，$n\le 10^6$。