游乐园 (game)

【题目描述】

小明来到了一个游乐园，里面有 $n$ 个项目，每个项目都有一个等第，用大写字母 A,B,c,D... 来表示。

每个项目等第有一个上限 $m_i$ ，即该项目获得的等第只能介于 A 和第 $m_i$ 个大写字母之间。

依次游玩了 $n$ 个项目后，小明就可以得到一个长度为 $n$ 的等第字符串。

而每天游乐园都会公布一个长度为 $n$ 的幸运字符串，当小明的等第字符串和幸运字符串的最长公共子序列长度大于等于 $n-2$ 时，小明将获得幸运大奖。

小明通过一些途径提前得知了今日的幸运字符串，他想知道一共有多少种字符串可以帮他获得幸运大奖。

【输入格式】

第一行一个整数 $n$，表示字符串的长度

第二行 $n$ 个整数，表示能获得的等第的上限

第二行一个字符串$s$

【输出格式】

一个整数表示答案，对998244353取模

【样例 $1$ 输入】

3
3 3 2
AAB

【样例 $1$ 输出】

18

样例解释：等第字符串一共有18种可能，每个等第字符串与答案字符串的最长公共子序列长度至少为1,故而答案为18。

【样例 $2$】

见下发文件

【样例 $3$】

见下发文件

【数据范围】

对于$20\%$的数据，$1\le n\le 4$。

对于$80\%$的数据，$1\le n\le 10^4$

对于$100\%$的数据，$1\le n\le 10^5,1\le m_i\le 26$，$s_i\in A\sim Z$。