Vasya 正在玩他最喜欢的长度为 $n$ 的字符串 $s$。他有一个他最喜欢的数字序列，其中每个数字都是一个有理数 $n_i/d_i \in [0, 1]$。对于 $1$ 到 $n$ 的每个 $i$，Vasya 取一个等于 $s$ 的长度为 $i$ 的前缀的字符串，以 $1 - n_i/d_i$ 的概率将其反转，并将得到的字符串放入一个集合中。然后，他根据集合中的字符串构建一棵字典树（trie，定义见说明）。他请你计算所得字典树中顶点的期望数量。
输入格式
第一行包含一个整数 $n$，表示字符串的长度 ($1 \le n \le 2 \cdot 10^5$)。第二行包含一个长度为 $n$ 的字符串 $s$，由小写英文字母组成。第三行包含恰好 $|s|$ 个整数 $p_i$ ($0 \le p_i < 998\,244\,353$)，其中 $p_i$ 等于 $n_i d_i^{-1} \pmod{998\,244\,353}$。
输出格式
输出一个整数，即问题的答案对 $998\,244\,353$ 取模的结果。也就是说，如果期望的顶点数量等于不可约分数 $a/b$，你应该输出 $ab^{-1} \pmod{998\,244\,353}$。可以证明答案是有理数，并且如果答案的不可约形式为 $a/b$，则在题目给定的约束条件下，$b$ 不能被 $998\,244\,353$ 整除。
样例
样例 1
2 aa 324 435
3
样例 2
2 ab 499122177 499122177
499122180
样例 3
6 wordle 23 45 67 89 87 65
376824090
样例 4
7 abacaba 0 1 598946612 332748118 598946612 1 0
266198508
样例 5
6 banana 0 0 0 0 0 0
16
样例 6
7 trytrie 1 1 1 1 1 1 1
8
说明
在第一个样例中，集合将始终由两个字符串 a 和 aa 组成，因此字典树中的顶点数将始终等于 $3$。
在第二个样例中，集合将是 $\{a, ab\}$ 或 $\{a, ba\}$，每种情况的概率均为 $1/2$。期望的顶点数将等于 $3.5$。
基于一组不同字符串 $s_1, \dots, s_n$ 构建的字典树（trie）是一棵特殊的有根树，边上写有字母，且部分顶点被标记。该树具有以下性质：
- 所有叶子节点都被标记。
- 恰好有 $n$ 个被标记的顶点。
- 从同一个顶点出发的任意两条边，其上的字母都不相同。
- 通过写下从根到被标记顶点的路径上的字母所得到的字符串集合，与 $\{s_1, \dots, s_n\}$ 一致。