Unique Necklace Patterns

Laosb, after celebrating the 1st anniversary of his pairing success with scjyholy, spent all his savings to buy a necklace for scjyholy. However, he found the store's necklace styles too limited and decided to reassemble the beads into a unique pattern that would truly touch scjyholy.

After removing all the beads from the original necklace, Laosb selects some of the beads (at least one) in order (from left to right) to form a new necklace. Since the beads come in various colors, he wonders how many different patterns he can create. Two patterns are considered different if the sequence of colors differs.

For example, consider a necklace with 3 beads: blue, yellow, blue. The possible distinct selections are:

• blue
• yellow
• blue-yellow
• blue-blue
• yellow-blue
• blue-yellow-blue

The answer might be very large, so output the result modulo $M$.

Hint: Let $dp[i]$ be the number of distinct subsequences (including the empty subsequence) for the first $i$ beads. Then,

$$dp[i]=\begin{cases}2\cdot dp[i-1] & \text{if the } i\text{-th bead has not appeared before},\\ 2\cdot dp[i-1]-dp[\text{last}(s_i)] & \text{if it has appeared before},\end{cases}$$

and the final answer is $dp[n]-1$ modulo $M$.

inputFormat

The first line contains two integers n and M where n is the number of beads in the necklace and M is the modulus.

The second line contains n strings separated by spaces, representing the colors of the beads in order.

outputFormat

Output a single integer which is the number of different necklace patterns that can be formed, taken modulo M.

sample

3 100
blue yellow blue

6