#1047. 二进制序列

二进制序列是指仅包含字符 0 或 1 的序列。

假设 是一个二进制序列，定义函数 表示 的最长不下降子序列的长度。例如，。

现在，输入一个正整数 ，然后随机生成一个长度恰好为 的二进制序列 。你需要计算 的期望值。可以证明答案可以写成一个最简分数 的形式，你需要输出这个分数对质数 取模之后的结果，即输出 ，其中 表示 在 下的逆元。

输入仅一行两个正整数 ，分别表示随机生成的二进制序列 以及取模的质数 。

输出一行一个整数，表示答案 对 取模之后的结果。

样例输入 1

2 998244353

样例输出 1

249561090

样例输入 2

3 998244853

样例输出 2

499122429

样例解释

对于 ，随机生成的序列的所有可能为：00 01 10 11，其对应的函数值分别为 ，所以答案为 。

• 对于 30% 的数据，
• 对于 60% 的数据，
• 对于 90% 的数据，
• 对于 100% 的数据，，输入保证 是一个质数。