AT_arc221_b.Two-Powered Sum

You are given a positive integer $N$ and a prime $P$.

There is a length-$N$ sequence $A=(A_1,A_2,\ldots,A_N)$ where all elements are $0$.

You can repeat the following operation any number of times, possibly zero:

• Choose a non-empty subset $S$ of $\lbrace 1,2,\ldots,N\rbrace$. Let $\displaystyle x=\sum_{i\in S}2^{i-1}$. For each $i\in S$, replace $A_i$ with $x$.

Find the number, modulo $P$, of possible sequences $A$ after repeating the operations.

给你一个正整数 $N$ 和一个质数 $P$。

有一个长度为 $N$ 的序列 $A=(A_1,A_2,\ldots,A_N)$，其中所有元素初始均为 $0$。

你可以任意次（包括零次）执行以下操作：

• 选择集合 $\lbrace 1,2,\ldots,N\rbrace$ 的一个非空子集 $S$。令 $\displaystyle x=\sum_{i\in S}2^{i-1}$。对每个 $i\in S$，将 $A_i$ 替换为 $x$。

求经过若干次操作后，可能得到的不同序列 $A$ 的个数（对 $P$ 取模）。

The input is given from Standard Input in the following format:

$N$ $P$

输入从标准输入中以如下格式给出：

$N$ $P$

Output the answer.

输出答案。

Sample 1 Explanation:
The possible sequences $A$ are $(0),(1)$, giving two possibilities.

Sample 2 Explanation:
The possible sequences $A$ are $(0,0),(0,2),(1,0),(1,2),(1,3),(3,2),(3,3)$, giving seven possibilities.

Constraints

• $1\leq N\leq 700$
• $P$ is a prime satisfying $10^8\lt P\lt 10^9$.
• All input values are integers.

样例 1 解释：
可能的序列 $A$ 为 $(0)$、$(1)$，共两种可能。

样例 2 解释：
可能的序列 $A$ 为 $(0,0)$、$(0,2)$、$(1,0)$、$(1,2)$、$(1,3)$、$(3,2)$、$(3,3)$，共七种可能。

约束条件

• $1\leq N\leq 700$
• $P$ 是一个满足 $10^8\lt P\lt 10^9$ 的质数。
• 所有输入值均为整数。