Majority
Contest: CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2700
Tags: combinatorics, dp, math, strings

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 < 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$$$.

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Note:
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$$$.

In the third sample, the rated strings are:

- 1001;
- 1111;
- 1011;
- 1101.

Example input:
2 100

Example output:
1

Example input:
3 10

Example output:
2

Editorial:
First off, let's try to reduce the given operation to a simpler form. We claim that if it is possible to make the string $$$111...111$$$ using the specified operation, we can make it $$$111...111$$$ by doing the following new operation : Select two indices $$$(i,j)$$$ such that the substring $$$s_{i...j}$$$ looks like this $$$111..100...001...111$$$ and make it all one. The proof is just to show that if we can perform operation $$$(i,j)$$$, then it must exist some substring of $$$s_{i...j}$$$ respecting the propriety of the new operation.
Let $$$dp_{i,j}$$$ be the number of binary strings that can begin with a prefix of length j full of ones, and after the prefix, we hit a roadblock ( we cannot extend it more than this ). For transitions, we have to iterate through the length of the roadblock and the length of the fixable prefix right after it, but there is one problem – we cannot compute $$$dp_{i,i}$$$ using any recurrence relation. Fortunately, we can compute it by subtracting the ways we get roadblocks, because, by definition $$$dp_{i,i}$$$ can be turned into $$$111...111$$$ which doesn't have any roadblocks at all. This is $$$O(N^4)$$$ if implemented naively, but one can optimize it to $$$O(N^2)$$$ by keeping prefix sums over prefix sums.