UOJ Logo Universal Online Judge

UOJ

#516. 【美团杯2020测试赛】子序列

统计

可怜发现了一种快速构造超长字符串的方法。

最开始,可怜手上有一个空串 $s_0$,接着,可怜对这个串进行了 $n$ 次操作。在第 $i$ 次操作的时候,可怜选择了一个字符 $c$,并利用 $s_{i-1}$ 和 $c$ 构造了字符串 $s_i = cs_{i-1}[1]cs_{i-1}[2] \dots s_{i-1}[m]c$,其中 $m$ 为串 $s_{i-1}$ 的长度。

举例来说,如果 $n=3$ 且可怜选择的字符分别是 $a,b,c$,则 $s_n=cbcacbc$。

现在,可怜想要知道,字符串 $s_n$ 本质不同的非空子序列有多少个。(注意不能为空,但可能是 $s_n$ 本身)。

串 $s$ 是串 $t$ 的子序列当且仅当串 $s$ 可以通过删去 $t$ 中的某些字符得到。

输入格式

第一行输入一个整数 $n(1 \leq n \leq 2000)$,表示可怜进行的操作次数。

第二行输入一个长度为 $n$ 的小写字符串 $s$,其中 $s_i$ 表示可怜在第 $i$ 轮选择的字符。

输出格式

输出一行一个答案,表示 $s_n$ 中本质不同的子序列个数,答案可能很大,对 $998244353$ 取模后输出。

样例一

input

2
ab

output

6

样例二

input

10
aaaaaaaaaa

output

1023

限制与约定

Small Task: $n\leq 20$。

Large Task: $n \leq 2000$。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载