[ZJOI2010]排列计数

内存限制：256 MB 时间限制：1000 ms

称一个 $1,2,...,N$ 的排列 $P_1,P_2,...,P_n$ 是 Magic 的，当且仅当 $2 \le i \le N$ 时，$P_i>P_{i/2}$。计算 $1$，$2$，$...N$ 的排列中有多少是 Magic 的，答案可能很大，只能输出模 $P$ 以后的值。

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

输出中仅包含一个整数，表示计算 $1,2,⋯, $ 的排列中，Magic 排列的个数模 $p$ 的值。

样例输入 1

20 23

样例输出 1

100% 的数据中，$1 ≤ N ≤ 10^6, P≤ 10^9$，$p$ 是一个质数。数据有所加强。