P2267 琪琪的项链
题目背景
Piet项目的一对开发者laosb(吕世博)与scjyholy(叶嘉琪)最近一直为中国学生站长联盟的童鞋们所津津乐道，不仅仅因为他们天天在某群中秀恩爱，而且他们还经常被用作题目背景。现在我们以他们为背景来引出一道问题。
题目描述
话说laosb在与scjyholy配对成功1周年后，laosb花光了其所有的积蓄，为scjyholy买了一条项链。但是，他发现店中项链的样式实在太少，于是他想买回一条项链，组成自己的独特样式，以使scjyholy感动。
首先laosb把项链中所有珠子取下，然后从左到右，选出若干珠子（至少1颗），组成新的项链。因为项链珠子有很多颜色，laosb希望知道他一共能组合出多少种不同的样式。
如图所示，假设原始的项链有3颗珠子：蓝、黄、蓝，这样他一共有如下的选择方法：
由于答案可能很大，请输出答案 mod M的结果。
输入格式
无
输出格式
无
说明/提示
0 < N ≤ 500000
0 < M < 10^9