4. 排列计数

【题目描述】

称一个 $1 \sim n$ 的排列 $p_1,p_2, \dots ,p_n$ 是 Magic 的，当且仅当  

$$\forall i \in [2,n],p_i > p_{\lfloor i/2 \rfloor}$$

计算 $1 \sim n$ 的排列中有多少是 Magic 的，答案可能很大，只能输出模 $m$ 以后的值。

【输入格式】

一行两个整数 $n,m$，含义如上所述。

【输出格式】

输出文件中仅包含一个整数，表示 $1\sim n$ 的排列中， Magic 排列的个数模 $m$ 的值。

【样例输入1】

20 23

【样例输出1】

16

【样例2】

点击下载样例2

【数据规模与约定】

对于 $30\%$ 的数据，$1\le n \le 10$, $1\le m \le 10^9$。

对于 $100\%$ 的数据，$1\le n \le 10^6$, $1\le m \le 10^9$，$m$ 是一个质数。