Description

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

Input Format

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 Format

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

3 100
1 888 1

6

4 100
1 2 3 4

15

Hint

Translated by ChatGPT 5