CF1750F.Majority

Everyone was happy coding, until suddenly a power shortage happened and the best competitive programming site went down. Fortunately, a system administrator bought some new equipment recently, including some UPSs. Thus there are some servers that are still online, but we need all of them to be working in order to keep the round rated.

Imagine the servers being a binary string $s$ of length $n$. If the $i$-th server is online, then $s_i = 1$, and $s_i = 0$ otherwise.

A system administrator can do the following operation called electricity spread, that consists of the following phases:

• Select two servers at positions $1 \le i \lt j \le n$ such that both are online (i.e. $s_i=s_j=1$). The spread starts only from online servers.
• Check if we have enough power to make the spread. We consider having enough power if the number of turned on servers in range $[i, j]$ is at least the number of turned off servers in range $[i, j]$. More formally, check whether $2 \cdot (s_i + s_{i+1} + \ldots + s_j) \ge j - i + 1$.
• If the check is positive, turn on all the offline servers in range $[i, j]$. More formally, make $s_k := 1$ for all $k$ from $i$ to $j$.

We call a binary string $s$ of length $n$ rated if we can turn on all servers (i.e. make $s_i = 1$ for $1 \le i \le n$) using the electricity spread operation any number of times (possibly, $0$). Your task is to find the number of rated strings of length $n$ modulo $m$.

所有人都在愉快地编程，直到突然发生停电，导致最佳的编程竞赛网站宕机了。幸运的是，一名系统管理员最近购买了一些新设备，其中包括若干台不间断电源（UPS）。因此，目前仍有部分服务器处于在线状态，但我们需要让所有服务器都恢复正常运行，才能保证本次比赛的评分有效。

将服务器状态建模为一个长度为 $n$ 的二进制字符串 $s$：若第 $i$ 台服务器在线，则 $s_i = 1$；否则 $s_i = 0$。

系统管理员可以执行一种称为“电力扩散”（electricity spread）的操作，该操作包含以下步骤：

• 选择两个位置 $1 \le i \lt j \le n$ 的服务器，且二者均在线（即满足 $s_i = s_j = 1$）。扩散仅能从已在线的服务器开始。
• 检查是否有足够电力支持此次扩散。当区间 $[i, j]$ 内已开启的服务器数量不少于已关闭的服务器数量时，视为电力充足。更准确地说，需满足：
  $2 \cdot (s_i + s_{i+1} + \ldots + s_j) \ge j - i + 1$。
• 若上述条件成立，则将区间 $[i, j]$ 内所有离线服务器全部开启。即对所有 $k \in [i, j]$，令 $s_k := 1$。

我们称一个长度为 $n$ 的二进制字符串 $s$ 是“可评分的”（rated），如果可以通过任意多次（包括零次）执行电力扩散操作，使得所有服务器均被开启（即对所有 $1 \le i \le n$，均有 $s_i = 1$）。你的任务是：计算长度为 $n$ 的可评分字符串的个数，并对 $m$ 取模。

The first and only line contains two integers $n$ and $m$ ($1 \le n \le 5000$, $10 \le m \le 10^9$) — the length of the string and the required module.

第一行且唯一一行包含两个整数 $n$ 和 $m$（$1 \le n \le 5000$，$10 \le m \le 10^9$）—— 分别表示字符串的长度和所需的模数。

Print a single integer — the number of rated binary strings of length $n$. Since this number can be large, print it modulo $m$.

输出一个整数——长度为 $n$ 的有评级二进制字符串的个数。由于该数可能很大，请对 $m$ 取模后输出。

In the first example, the only rated string is 11. So the answer is $1$.

In the second example, the rated strings are:

• 111;
• 101, because we can perform an operation with $i = 1$ and $j = 3$.

So the answer is $2$.

In the third sample, the rated strings are:

• 1001;
• 1111;
• 1011;

So the answer is $4$.

在第一个例子中，唯一的达标字符串是 11。因此答案为 $1$。

在第二个例子中，达标字符串有：

• 111；
• 101，因为我们可对 $i = 1$ 和 $j = 3$ 执行一次操作。

因此答案为 $2$。

在第三个样例中，达标字符串有：

• 1001；
• 1111；
• 1011；
• 1101。

因此答案为 $4$。