P2606 [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$ 以后的值。

无

无

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