题目背景

Piet项目的一对开发者laosb(吕世博)与scjyholy(叶嘉琪)最近一直为中国学生站长联盟的童鞋们所津津乐道，不仅仅因为他们天天在某群中秀恩爱，而且他们还经常被用作题目背景。现在我们以他们为背景来引出一道问题。

题目描述

话说laosb在与scjyholy配对成功1周年后，laosb花光了其所有的积蓄，为scjyholy买了一条项链。但是，他发现店中项链的样式实在太少，于是他想买回一条项链，组成自己的独特样式，以使scjyholy感动。

首先laosb把项链中所有珠子取下，然后从左到右，选出若干珠子（至少1颗），组成新的项链。因为项链珠子有很多颜色，laosb希望知道他一共能组合出多少种不同的样式。

如图所示，假设原始的项链有3颗珠子：蓝、黄、蓝，这样他一共有如下的选择方法：

由于答案可能很大，请输出答案 mod M的结果。

输入格式

输入第1行，两个整数N、M，其中N为原始珠子数目。

输入第2行，N个非负整数，每个整数代表一颗珠子颜色，相同整数表示颜色相同。

输出格式

输出一个整数，表示样式总数 mod M的值。

3 100
1 888 1

6

4 100
1 2 3 4

15

提示

0 < N ≤ 500000

0 < M < 10^9