该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

nodgd 很喜欢树，Zyq 很喜欢拓扑。

描述

nodgd 十分强大，他给小蒟蒻 Zyq612 扔了一道题：求一颗完全二叉树树的拓扑排序数量。

由于 Zyq 太弱了，所以他找到了您，希望您帮他算算：给定完全二叉树的节点数，求拓扑排序数量。

由于结果可能很大，请您对一个 质数 \(p\) 取膜。

格式

输入格式

两个整数 \(n\)，\(p\) 。

输出格式

一个自然数，代表拓扑排序数量对 \(p\) 取模。

样例

输入

23 31

输出

28

数据范围

\(0 \le n \le 10^7 ，0 \le p \le 10^{18}\)