Description

$\mathrm{Ethan}$ has $n$ crystal balls. Now he arranges these crystal balls in a row. Each crystal ball has an energy value, and is either green or purple.

• In the following, $P$ stands for purple, and $G$ stands for green.

$\mathrm{Ethan}$ will take away these crystal balls in the following way:

1. Take away the leftmost crystal ball.

2. Suppose the removed crystal ball has color $c_1$ and energy $x_1$, the current leftmost remaining crystal ball has color $c_2$ and energy $x_2$, and the number of times a crystal ball has been removed is $cnt$ (including this time).

• If $c_1=c_2$, then $\mathrm{Ethan}$ will combine these two crystal balls into one large crystal ball (the crystal ball removed this time is still counted in the total answer; see samples for details), with color $c_1$ and energy value $x_1 \times x_2$, and put it at the left end of the crystal ball sequence.

• If $c_1=P,c_2=G,cnt\equiv 1\mathrm{\ (mod\ 2)}$, then $\mathrm{Ethan}$ will flip the colors of the remaining crystal balls (i.e., green becomes purple, and purple becomes green).

• If the above conditions still cannot be satisfied, then $\mathrm{Ethan}$ will reverse the remaining sequence of crystal balls.

He keeps doing this until only one ball remains. Then $\mathrm{Ethan}$ will directly take away the last ball. Find the sum of the energy values of all removed crystal balls.

Since the answer can be very large, take it modulo $p$.

Input Format

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

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

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

Output Format

Output one integer, the sum of the energy values of the removed crystal balls modulo $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

Hint

Sample Explanation

Sample $1$:

$\mathrm{Ethan}$ first removes the leftmost crystal ball, whose color is G. Add the number written on it to the answer, i.e., $1$. Then the remaining crystal balls are reversed, and the sequence becomes $4\ 3\ 2$ GGP. (Because $c_1=G,c_2=P$, and the removal count is odd, it does not satisfy conditions 1 or 2, so the sequence is reversed.)

Then remove the leftmost crystal ball, whose color is G. Add $4$ to the answer. Next, combine the current leftmost remaining crystal ball with the removed one into a large crystal ball with number $12$. The sequence becomes $12\ 2$ GP.

Remove the leftmost crystal ball, whose color is G. Add $12$ to the answer. Reverse the remaining sequence, which becomes $2$ P.

Remove the last crystal ball. Add $2$ to the answer. The final answer is $1+4+12+2=19$.

Sample $2$:

First remove $3$, $c_1=P,c_2=G,cnt=1$, so flip the colors.

Remove $7$, $c_2=c_3=P$, multiply $x_3$ by $x_2$, getting $x_3=35$.

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

Constraints and Notes

This problem uses $\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\%$.

For all testdata, the time limit is $1s$, and the memory limit is $16MB$.

Translated by ChatGPT 5