测试数据来自 nnu_contest/1311

G. Rotating-Calipers

时间限制：2s

空间限制：512MB

本题分数：350

题目背景

经典问题：“旋转卡壳”（一个算法的名称）有多少种读法

题目描述

现给出一个由小写字母组成的、不包含空格的文本串 \(s\) 和一个字典 \(D\) ，你需要通过以下方法解读 \(s\)：

• 将字符串进行分词，这个词必须在字典 \(D\) 中出现过；

• 为每个词分配一种读音。

问，有多少种不同的解读方法。

当以下条件的至少一个满足时，我们认为两种解读方法不同：

• 两种解读方法对于句子 \(s\) 的分词方法不同
• 对于某个 \(i\)，两种解读方法对第 \(i\) 个词分配的读音不同。

答案可能很大，对 \(998244353\) 取模。

输入格式

第一行一个整数\(n\)，表示字典中单词的个数。

接下来 \(n\) 行每行包含一个字符串和一个整数，表示一个单词及它的读音数量。

接下来一行一个字符串 \(s\) ，是需要进行解读的句子。

输出格式

一个正整数 \(ans\)，表示方案数，注意取模。

样例输入1

4 
x 2
z 3
q 2
k 2
xzqk

样例输出1

24

样例输入2

4
y 10
yy 5
ds 4
yyds 100000
yyds

样例输出2

100420

样例2解释

如果分词方法是 (y)(y)(ds)，则有 \(400\) 种读法

如果分词方法是 (yy)(ds)，则有 \(20\) 种读法

如果分词方法是 (yyds)，则有\(100000\)种读法。

总计\(100420\)种。

样例输入3

2
aa 1000
baa 10000
aaabaa

样例输出3

0

样例3解释

无法将句子分成字典中的单词。

样例输入4

144
a 9990777
asihhugoucrozrk 578
atbuqbmqplhdcsxh 1376
b 5589273
bavxfzkoykiewmdthrffrjxqzeatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucr 1273
bavxfzkoykiewmdthrffrjxqzeatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxihacoimxdaoopengfcasbekjahoscizqqnpbjtkmsc 990
bhjxrcojjkdkbavxfzkoykiewmdthrffrjxqzeatbuqbmqplhdcsxhizj 1986
bthwowmue 811
c 16118386
civhyllrcjgfxkynvc 511
cojjkdkbavxfzko 291
crozrkguvkizbzhqxihacoimxdaoopengfcasbekjahosci 542
csxhizjdleddizsqpfbthwowmuebpcoovlv 1700
d 6655124
daoopengfcasbekjahoscizqqnpbjtkms 450
dckcxpnrqumpxkvipeoyorbtvgwcz 1258
dixjmibmbkwzfmftxfjepjehdckcxpnrqump 954
dixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyor 1576
dthrffrjxqzeatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynr 1016
e 7045745
eatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoovlv 1457
ebshkyznpsnyinhcwhojr 238
ebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucrozrkgu 872
eddizsqpfbthw 1817
eoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmy 332
f 810199
fbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmib 368
fcasbekjahosciz 905
fzkoykiewmdthrffr 718
fzkoykiewmdthrffrjxqzeatbuqbmqpl 1227
g 18734918
guvkizbzhqxihaco 1773
h 3530987
hacoimxdaoopengfcasbekja 4
hdcsxhizjdleddizsqpfbthwow 966
hky 614
hrffrjxq 1945
hui 713
huiwclvzjvqlbesj 1568
hwowmuebpcoovlvuhuiwclvzjvqlbesju 859
hwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkw 26
hwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwz 1356
hyllrcjgfxkynvcumtuhcasihhugoucrozrkg 560
hyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxiha 176
hyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxihacoimxdaoop 1684
hynrhdmykwwcivhyllrcjgfxkynvcumtuhca 1224
i 3994762
ibmbkwzfmftxf 706
iewmdthrffrjxqzeatbuqbmqplhdcsxhizjd 669
ihhugoucrozrkguvkizbzhqxihacoimxdaoopen 247
ipeoyorbtvgwczv 890
ivhyllrcjg 1257
ixgqrwnijwdcyrebshkyznpsn 1647
ixjmibmbkwzfmf 1379
ixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgw 1514
izjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbe 1142
izqqnpbjtk 379
izsqpfbthwowmuebpcoovlvuhuiwcl 1593
j 8999693
jbhjxrc 97
jbhjxrcojjkdkbavxfzkoykiewmdthrffrjxqzeatbuq 809
jepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhug 1313
jxqzeatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoov 1496
jxrcojjkdkbavxfzkoykiewmdthrffrjxqzeatbuqbmqplh 254
k 2044756
kguvkizbzhqxiha 1429
kwwcivhyllrcjgfxkynvcumt 1576
kwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxihacoimxdaoopengfcas 868
kynvcumtuhcasihhugoucrozrkguvkiz 1740
l 8466011
lhdcsxhizjdled 161
llrcjgfxkynvcumt 125
lvuhuiwclvzjvqlbesjudix 1622
m 2426101
mdthrffrjxqzeatbuqbmqplhdcsxhizjdleddizsqpfb 193
mpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykww 1282
mt 1492
n 5999969
ngfcasbekjahoscizqqnpbj 935
nijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxihacoimxdaoope 1081
nvcumtuhcasihhugoucr 856
nvcumtuhcasihhugoucrozrkguvkizbzhqxihaco 1223
o 558853
oopeng 941
oovlvuhui 1670
opengfcasbekjahoscizqqnpbjtk 1292
ovlvuhuiwclvzjvqlbesjudixjmibmb 1378
owmuebpcoovlvuhuiwclvzjvqlbesjudixjmib 1529
owmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyre 1461
oykiewmdthr 1830
ozrkguvki 536
p 18888253
peoyorbtvgwczvixgqrwnijwdcyrebshkyznp 1962
plhdcsxhizjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxihacoimxda 879
pnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznp 1710
q 17302279
qbmqplhdcsxhizjdleddizsqpf 993
qbmqplhdcsxhizjdleddizsqpfb 231
qumpxkvipeoyorbtvgwczvixgqrwnijwd 588
qxihacoi 1425
r 1915083
rcojjkdkbavxfzkoykiewmdthrffrjxqzeatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxihacoimxdaoopeng 1348
rhdmykwwcivhyllrcjgfxkynvcumtuhc 1161
rjxqzeatb 717
rkguvkizbzhq 1948
rkguvkizbzhqxihacoimxdaoo 1274
s 12688225
sxhizjdleddizsqpfbthw 1085
t 5130583
thrffrjxqzeatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyi 765
tuhcasihhugoucrozrkguvki 1015
u 2960994
ucrozrkguvki 1141
uhuiwclvzjvqlbesjudixjmibmbkwzfmftxfje 269
uiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpn 1299
umpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivh 1752
uvkizbzhqxihacoimxdaoopengfcasbekjahoscizqqnpb 1397
v 10156483
vhyllrcjgfxkynvcumtuhcasihhugoucrozrkgu 982
vuhuiwclvzjvqlbesj 1894
w 8309059
wc 1675
wclvzj 944
wdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcj 787
whojrchynrhdmy 1464
whojrchynrhdmykwwcivhyllrcjgfxkynvcumt 1310
wowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwho 1258
wzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvg 370
x 9672400
xdaoopengfcasbekjahoscizqqnpbjtkm 1257
xgqrwnijwdcyrebsh 1405
xhizjdleddizsqp 414
xih 1230
xkvipeoyorbtvgwczvixgqrwnijwdcyrebshk 955
xkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyin 947
y 12976941
yllrcjgfxkynvcu 779
ynrhdmykwwcivhyllrcjgfxkynvcumt 400
yrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyll 1246
yznpsnyinhcwhojrchynrhdmykwwcivhyllr 707
z 15356569
zhqxihacoimxdaoopengfcasbekjahoscizqqnpbjtkm 231
zjdleddizsqpfbthwowmuebpcoovl 407
zjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpn 1908
lojbhjxrcojjkdkbavxfzkoykiewmdthrffrjxqzeatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxihacoimxdaoopengfcasbekjahoscizqqnpbjtkmscw

样例输出4

458938406

数据范围及限制

字典中的单词只包含小写字母，单词个数 \(1\le n\le 5000\)。

单词之间互不相等，即 \(i\neq j\to s_i\neq s_j\)

每个单词的解读方法数目\(1\le a_i\le 10^9\)

测试点编号	文本串长度\(\le \)	字典中单词长度之和 \(\le \)	其他约定	测试点分值
1	\(300\)	\(26\)	各单词的长度均为 \(1\)	每个测试点30分
2~3	\(300\)	\(5000\)	文本串仅包含一种字符	每个测试点30分
4~6	\(300\)	\(5000\)		每个测试点40分
7~8	\(3000\)	\(500000\)		每个测试点70分