排列计数

题目描述:

我们称一个的排列是Magic的，当且仅当2<=i<=N时，P[i]>P[i/2](P[i]表示排列的第i个位置上的数)。你的任务非常简单：计算N个数的排列中，有多少是Magic的。由于答案可能很大，你只需要输出模P以后的值即可。

输入格式:

第一行包含两个整数n和p，含义如上所述。

输出格式:

仅包含一个整数，表示计算的排列中，Magic排列的个数模p的值。

样例输入:

20 23

样例输出:

16

提示:

100%的数据中1<=N<=10⁶，P<=10⁹，p是一个质数。

时间限制: 1000ms
空间限制: 256MB

---

来源: 浙江省选2010day2t1