暂无测试数据。

Background

如果一棵树除了叶节点外每个节点都恰有两个子节点，那么称它为一棵满二叉树。

Description

一棵k-超级树可按如下方法得到：取一棵深度为k的满二叉树，对每个节点，向它的所有祖先连边（如果这条边不存在的话）。
现在你的任务是统计一棵k-超级树中有多少条每个节点最多经过一次的不同有向路径。两条路径被认为不同，当且仅当它们经过的节点的集合不同，或经过的节点的顺序不同。由于答案可能很大，请输出总路径数对mod取模后的结果。

Format

Input

一行两个整数k、mod，意义见上。

Output

一行一个整数，代表答案。

Sample 1

Input

2 100

Output

9

Sample 2

Input

3 1000

Output

245

Sample 3

Input

20 998244353

Output

450500168

Explanation

对第一组样例，将节点按前序遍历编号，共有9条不同的路径：1,2,3,1−2 ,2−1,1−3,3−1,2−1−3,3−1−2。

Limitation

对于10%的数据，k ≤ 4。
对于40%的数据，k ≤ 10。
对于60%的数据，k ≤ 100。
另有10%的数据，mod = 998244353。
对于所有数据，1 ≤ k ≤ 300，1 ≤ mod ≤ 109。
1s, 256000KiB for each test case.

Hint

Source

CDQZ TEST