Problem Background

Ethan has some crystal balls that can release powerful energy, and he plans to use these crystal balls to synthesize a magic that can destroy enemies.

• $a \equiv b \ (\text{mod} \ m)$ denotes that $a$ and $b$ are congruent modulo $m$, meaning $(a - b) / m$ is an integer.

Problem Description

Ethan has $n$ crystal balls, which he arranges in a row. Each crystal ball has an energy value and is either green or purple.

• Here, $P$ represents purple, and $G$ represents green.

Ethan will remove these crystal balls according to the following rules:

1. Remove the crystal ball at the leftmost end.

2. Suppose the color of the removed crystal ball is $c_1$, its energy value is $x_1$, the color of the new leftmost crystal ball is $c_2$, its energy value is $x_2$, and the number of times the crystal balls have been removed is $cnt$ (including this time).

• If $c_1 = c_2$, Ethan will combine these two crystal balls into a larger crystal ball (the removed crystal ball is still counted in the total number of removals, see the examples for details), with color $c_1$ and energy value $x_1 \times x_2$, placed at the leftmost end of the sequence.

• If $c_1 = P, c_2 = G,$ and $\equiv 1 \ (\text{mod} \ 2)$, Ethan will invert the colors of the remaining crystal balls (green becomes purple and purple becomes green).

• If none of the above conditions are met, Ethan will reverse the sequence of the remaining crystal balls.

This process continues until only one crystal ball remains, at which point Ethan will directly remove the last ball. Your task is to find the sum of the energy values of the removed crystal balls, modulo $p$.

Input Format

The first line contains two positive integers $n$ and $p$, representing the number of crystal balls and the modulus, respectively.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, where $a_i$ represents the energy value of the $i$-th crystal ball.

The third line contains a string consisting of the characters $P$ and $G$. If the $i$-th character is P, the crystal ball is purple; otherwise, it is green.

Output Format

A single integer representing the sum of the energy values of the removed crystal balls modulo $p$.

Sample Input and Output

Sample Input #1

4 998244353
1 2 3 4
GPGG

Sample Output #1

19

Sample Input #2

3 998244353
3 7 5
PGG

Sample Output #2

45

Sample Input #3

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

Sample Output #3

104157290

Notes

Sample Explanation

Sample 1:

Ethan first removes the leftmost crystal ball, which is G, and adds its value, $1$, to the answer. The remaining sequence is reversed to become $4 3 2$ GGP. (Since $c_1 = G, c_2 = P$, and the number of removals is odd, conditions 1 and 2 are not met, so the sequence is reversed).

He then removes the leftmost crystal ball again, which is G, and adds $4$ to the answer. He then combines the remaining leftmost crystal ball with the removed one to form a larger crystal ball with value $12$, resulting in the sequence $12 2$ GP.

He removes the leftmost crystal ball, which is G, and adds $12$ to the answer. The remaining sequence is reversed to become $2$ P.

He removes the last crystal ball, adding $2$ to the answer. The final answer is $1 + 4 + 12 + 2 = 19$.

Sample 2:

He first removes $3$, $c_1 = P, c_2 = G, cnt = 1$, and inverts the colors.

He then removes $7$, $c_2 = c_3 = P$, and multiplies $x_3$ by $x_2$, resulting in $x_3 = 35$.

He removes $35$, and the final answer is $3 + 7 + 35 = 45$.

Data Range and Constraints

This problem uses a subtask system.

• Subtask 1: $n \leq 2000, a_i \leq 10^9, p \leq 10^9, 15\%$.
• Subtask 2: $n \leq 5 \times 10^4, a_i \leq 10^9, p \leq 10^9, 15\%$.
• Subtask 3: $n \leq 5 \times 10^4, a_i \leq 10^{18}, p \leq 10^{18}, 20\%$.
• Subtask 4: $n \leq 10^6, a_i \leq 10^9, p \leq 10^9, 20\%$.
• Subtask 5: $n \leq 10^6, a_i \leq 10^{18}, p \leq 10^{18}, 30\%$.

For all test cases, the time limit is $1$ second, and the memory limit is $16$ MB.

见题面 Input 部分

见题面 Output 部分