Ethan's Crystal Ball Energy Sum

Ethan has n crystal balls arranged in a row. Each crystal ball has an energy value, and its color is either green or purple.

We denote P for purple and G for green.

Ethan removes the crystal balls one by one according to the following procedure until only one ball remains. Finally, he removes the last ball. The task is to calculate the sum of the energy values of all the balls that have been removed and output the result modulo p.

The procedure is as follows:

1. Remove the leftmost crystal ball.
2. Let the removed ball have color \(c_1\) and energy \(x_1\). If there is still a ball remaining, let the new leftmost ball have color \(c_2\) and energy \(x_2\). Let cnt be the number of removals performed so far (including the current one).
3. Then perform one of the following actions (note that only the ball removed in step 1 is counted towards the answer in this move):
   1. If \(c_1 = c_2\), remove the ball with \(c_2\) from the sequence and merge it with the previously removed ball to create a new ball. The new ball has color \(c_1\) and energy \(x_1 \times x_2\). Insert this merged ball at the beginning of the sequence.
   2. If \(c_1 = P\), \(c_2 = G\), and \(cnt \equiv 1 \pmod{2}\), then flip the colors of all remaining balls (i.e. change green to purple and purple to green).
   3. If neither of the above conditions is met, reverse the order of the remaining crystal balls.
4. Repeat the process until there is only one ball left. Remove the last ball and add its energy value to the answer.

Since the answer can be very large, output the total energy sum taken modulo \(p\).

Note: Even though in the merging operation the second ball is consumed, only the ball removed in step 1 for that move is directly counted. The energy of the merged ball (which is \(x_1 \times x_2\)) will be added when it is eventually removed in a subsequent operation.

inputFormat

The first line contains two integers \(n\) and \(p\) (1 ≤ n ≤ 10⁵ and \(1 ≤ p ≤ 10⁹\)), representing the number of crystal balls and the modulo value respectively.

Each of the next \(n\) lines contains a character and an integer separated by a space. The character is either G (green) or P (purple), and the integer represents the energy value of that crystal ball.

The crystal balls are given in the order from left to right.

outputFormat

Output a single integer: the sum of the energy values of all removed crystal balls, taken modulo \(p\).

sample

3 100
G 2
G 3
P 7

15