CF1750F Majority

每个人都在愉快地编程，直到突然发生了电力短缺，最好的竞赛编程网站宕机了。幸运的是，系统管理员最近购买了一些新设备，包括一些 UPS。因此，仍有一些服务器在线，但我们需要所有服务器都正常工作，才能让本轮比赛计分。 可以将服务器看作一个长度为 $n$ 的二进制字符串 $s$。如果第 $i$ 台服务器在线，则 $s_i=1$，否则 $s_i=0$。 系统管理员可以进行如下称为“电力传播”的操作，操作包括以下几个阶段： - 选择两个位置为 $1 \le i < 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$ 从 $i$ 到 $j$，令 $s_k := 1$。 我们称长度为 $n$ 的二进制字符串 $s$ 是“计分的”，如果可以通过若干次（可能为 $0$ 次）电力传播操作，将所有服务器都开启（即对所有 $1 \le i \le n$，有 $s_i=1$）。你的任务是计算长度为 $n$ 的计分二进制字符串的数量，结果对 $m$ 取模。

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

输出一个整数，表示长度为 $n$ 的计分二进制字符串的数量。由于答案可能很大，请输出对 $m$ 取模后的结果。

在第一个样例中，唯一的计分字符串是 11。所以答案是 $1$。 在第二个样例中，计分字符串有： - 111； - 101，因为可以对 $i=1$，$j=3$ 进行一次操作。 所以答案是 $2$。 在第三个样例中，计分字符串有： - 1001； - 1111； - 1011； - 1101。 所以答案是 $4$。 由 ChatGPT 4.1 翻译