UOJ Logo

NOI.AC

1S 512MB

#2052. 子序列

Statistics

子序列

【问题描述】

你有一个长为$n$的小写字母字符串$s$,第$i$个字符有$a_i\%$的概率被删掉。

求期望的本质不同的子序列个数(包括空串)。

字符串$s$是字符串$t$的子序列当且仅当$s$可以由$t$删掉若干字符得到。

你需要将答案对$998244353$取模。

【输入格式】

从文件 sub.in 中读入数据。

第一行一个整数$n$

第二行一个长度为n的小写字母字符串s. 第三行$n$个数$a_1,a_2...a_n$

【输出格式】

输出到文件 sub.out 中。 输出一个整数,表示答案

【样例输入】

4

abdb

50 50 50 50

【样例输出】

311951365

【数据规模】

对于%30的数据,有1 ≤ n ≤ 10

对于%50的数据,有1 ≤ n ≤ 1000

对于%100的数据,有1 ≤ n ≤ 100000,0 ≤ $a_i$ ≤ 100

【时空限制】

1s,256MB

【友情提示】

模998244353域下100的逆元是828542813