P2267 Qiqi's Necklace

A pair of developers of the Piet project, laosb (Lv Shibo) and scjyholy (Ye Jiaqi), have recently become a hot topic among the members of the Chinese Student Webmasters Union, not only because they show their affection every day in a certain chat group, but also because they are often used as problem backgrounds. Now we use them as the background to introduce a problem.

After the $1$-year anniversary of pairing up with scjyholy, laosb spent all his savings to buy a necklace for scjyholy. However, he found that the store had too few styles, so he wanted to buy one and assemble his own unique style to move scjyholy. First, laosb removes all the beads from the necklace. Then, from left to right, he selects some beads (at least $1$ bead) to form a new necklace. Because there are many bead colors, laosb wants to know how many different styles he can form in total. As shown in the figure, suppose the original necklace has $3$ beads: blue, yellow, blue. Then he has the following choices:  Since the answer can be large, please output the result $\bmod\ M$.

The first line contains two integers $N,M\ (1 \le N \le 5 \times 10^5,1 \le M \le 10^9)$, where $N$ is the number of original beads. The second line contains $N$ non-negative integers $A_i\ (0 \le A_i \le 10^9)$, each representing the color of a bead. Equal integers indicate the same color, and different integers indicate different colors.

Output a single integer: the total number of styles $\bmod\ M$.

Translated by ChatGPT 5