无额外样例。

题目描述

给出一个整数 n，让你构造一个数列 A，满足：

（1） A 是 1 ~ n 的一个排列；

（2） 对于 ∀ i ( 1 < i ≤ n ) 有 $A_i$ > $A_{⌊i/2⌋}$，其中 $⌊ ⌋$ 表示下取整。

问：你能构造出多少个不同的数列 A？

答案可能很大，你需要将其 mod p 后输出。p 是一个质数。

输入

一行，两个整数 n, p

输出

一行，一个整数，表示答案 mod p

样例1输入

3 5

样例1输出

2

样例2输入

1000000 998244353

样例2输出

773860226

数据范围

100% 的数据：n ≤ $10^6$, p ≤ $10^9$, 输入数据保证 p 是一个质数。