P2606 [ZJOI2010] Permutation Counting

We call a permutation $p_1, p_2, \dots, p_n$ of $1 \sim n$ "Magic" if and only if $$\forall i \in [2,n], \; p_i > p_{\lfloor i/2 \rfloor}.$$ Count how many permutations of $1 \sim n$ are "Magic". The answer may be large; output the value modulo $m$.

One line contains two integers $n, m$, as described above.

Output a single integer: the number of "Magic" permutations of $1 \sim n$ modulo $m$.

Constraints For $100\%$ of the data, $1 \le n \le 10^6$, $1 \le m \le 10^9$, and $m$ is a prime. Translated by ChatGPT 5