抓字符
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

有n个字符跑掉了，需要尽可能的将它们抓回来。(请注意不同寻常的内存限制）
每个字符被抓的概率为\frac{1}{p_i} (p_i以整数给出)，你会把抓到的字符串成一串，如果这个字符串的字典序满足[非严格]单调，那么这个串就是好的。
如果字符按顺序抓取，那么最终得到的好串的概率是多少。(答案对998244353取模)
空串不是好串。
(字符都为小写英文字母)

输入描述:

第1行输入一个整数n表示字符的数量。(1 \leq n \leq 1000000)
第2行输入一个字符串S，s_i表示第i个字符。
第3行输入n个整数p_i。(1 \leq p_i \leq 1000000)

输出描述:

输出得到好串的概率。
示例1

输入

复制 
4
abcd
2 2 2 2

输出

复制 
62390273

说明

只有空串不是好串，空串概率为\frac{1}{16},好串概率为\frac{15}{16}。

备注:

(答案对998244353取模)