Problem Background

A pair of developers from the Piet project, laosb (Lü Shibo) and scjyholy (Ye Jiaqi), have been the talk of the town among students in the Chinese Student Webmaster Alliance. Not only do they frequently show affection in a group chat, but they are also often used as the background for problems. Now, we will use them as the background to introduce a problem.

Problem Description

After a year of being together, laosb spent all his savings to buy a necklace for scjyholy. However, he found that the styles of the necklaces in the store were too limited, so he wanted to buy a necklace and create his own unique style to impress scjyholy.

First, laosb removed all the beads from the necklace, then from left to right, he selected several beads (at least one) to form a new necklace. Since the beads come in many colors, laosb wants to know how many different styles he can create.

As shown in the figure, suppose the original necklace has 3 beads: blue, yellow, blue. He has the following selection methods:

Since the answer may be very large, please output the result modulo M.

Input Format

The first line contains two integers, N and M, where N is the number of original beads.

The second line contains N non-negative integers, each representing a bead color, with the same integer indicating the same color.

Output Format

Output a single integer, which is the total number of styles modulo M.

Sample Input and Output

Sample Input #1

3 100
1 888 1

Sample Output #1

6

Sample Input #2

4 100
1 2 3 4

Sample Output #2

15

Notes

0 < N ≤ 500000

0 < M < 10^9

见题面 Input 部分

见题面 Output 部分