[ZJOI2010]排列计数

题目描述

称一个 $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

说明

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