#1960. [ZJOI2010] 排列计数

[ZJOI2010] 排列计数

题目描述

称一个 1∼n1 \sim n 的排列 p1,p2,…,pnp_1,p_2, \dots ,p_n 是 Magic 的,当且仅当

∀i∈[2,n],pi>p⌊i/2⌋\forall i \in [2,n],p_i > p_{\lfloor i/2 \rfloor}

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

输入格式

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

输出格式

输出文件中仅包含一个整数,表示 1∼n1\sim n 的排列中, Magic 排列的个数模 mm 的值。

样例

20 23 
16

题目来源:洛谷 P2606