题目背景

$\mathrm{Ethan}$ 有一些可以释放强大能量的水晶球，他将要用这些水晶球合成可以消灭敌人的魔法。

• $a\equiv b\mathrm{\ (mod\ m)}$ 表示 $a$ 和 $b$ 对模 $m$ 同余，即 $(a-b)/m$ 为整数。

题目描述

$\mathrm{Ethan}$ 有 $n$ 个水晶球，现在他将这些水晶球排成一行，每一个水晶球上面有一个能量值，且要么是绿色，要么是紫色。

• 下文中，$P$ 代表紫色，$G$ 代表绿色。

$\mathrm{Ethan}$ 现在要按以下方式取走这些水晶球：

1. 取走最左端的水晶球。

2. 假设取走的水晶球的颜色为 $c_1$，能值为 $x_1$，剩余最左端的水晶球的颜色为 $c_2$，能量为 $x_2$，取出水晶的次数为 $cnt$（包括这一次）。

• 如果 $c_1=c_2$，那么 $\mathrm{Ethan}$ 会将这两个水晶球合成为一个大水晶球（本次取出的水晶球仍计入答案总数内，详情见样例），颜色为 $c_1$，能量值为 $x_1 \times x_2$，放在水晶球序列的最左端。

• 如果，$c_1=P,c_2=G,cnt\equiv 1\mathrm{\ (mod\ 2)}$，那么 $\mathrm{Ethan}$ 会将剩下的水晶球的颜色反转（即绿色变紫色，紫色变绿色）。

• 如果仍不能满足上面的条件，那么 $\mathrm{Ethan}$ 会将剩下的水晶球序列翻转。

就这样，直到最后只剩下一个球，此时 $\mathrm{Ethan}$ 会直接取走最后一个球，求取走的水晶球的能量值之和。

由于答案很大，请对 $p$ 取模。

输入格式

第一行，两个正整数 $n,p$，分别表示水晶球的个数和模数。

第二行，$n$ 个正整数 $a_1,a_2,\dots,a_n$，$a_i$ 表示第 $i$ 个水晶球的能量值。

第三行，一个由字符 $P$ 和字符 $G$ 组成的字符串，如果第 $i$ 个字符为P，那么该水晶球是紫色，否则为绿色。

输出格式

一个整数，表示取走的水晶球的能量值之和对 $p$ 取模的值。

4 998244353
1 2 3 4
GPGG

19

3 998244353
3 7 5
PGG

45

10 998244353
12345 23456 34567 45678 56789 67890 78901 89012 90123 101234
GPPGPGGGPG

104157290

提示

---

样例说明

样例 $1$：

$\mathrm{Ethan}$ 首先会取出最左端的水晶球，颜色为 G，答案加上它上面所写上的数字，即 $1$，剩下的水晶球翻转，序列变为 $4\ 3\ 2$ GGP。（因为 $c_1=G,c_2=P$，取出水晶球的次数为奇数，不满足条件 $1,2$，所以序列翻转）。

再取出最左端的水晶球，颜色为 G，答案加上 $4$，接着把剩下来最左端的水晶球与取走的水晶球合并成一个大的水晶球，写上的数字为 $12$，序列变为 $12\ 2$ GP。

取出最左边的水晶球，颜色为 G，答案加上 $12$，剩下的水晶球序列翻转，序列变为 $2$ P。

取出最后一个的水晶球，答案加上 $2$，最终答案为 $1+4+12+2=19$。

样例 $2$：

先取出 $3$，$c_1=P,c_2=G,cnt=1$，颜色翻转

取出 $7$，$c_2=c_3=P$，将 $x_3$ 乘上 $x_2$，得到 $x_3=35$

取出 $35$，最终答案为 $3+7+35=45$

---

数据范围与约定

本题采用 $\mathrm{Subtask}$ 制。

$\mathrm{Subtask}\ 1:n\leq 2000,a_i\leq 10^9,p\leq 10^9,15\%$。

$\mathrm{Subtask}\ 2:n\leq 5\times 10^4,a_i\leq 10^9,p\leq 10^9,15\%$。

$\mathrm{Subtask}\ 3:n\leq 5\times 10^4,a_i\leq 10^{18},p\leq 10^{18},20\%$。

$\mathrm{Subtask}\ 4:n\leq 10^6,a_i\leq 10^9,p\leq 10^9,20\%$。

$\mathrm{Subtask}\ 5:n\leq 10^6,a_i\leq 10^{18},p\leq 10^{18},30\%$。

---

对于所有测试点，时间限制 $1s$，空间限制 $16MB$。