P5672 "SWTR-2" Crystal Balls

$\mathrm{Ethan}$ has some crystal balls that can release powerful energy. He is going to use these crystal balls to combine magic that can destroy enemies. - $a\equiv b\mathrm{\ (mod\ m)}$ means that $a$ and $b$ are congruent modulo $m$, i.e., $(a-b)/m$ is an integer.

$\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$.

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

--- ### 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