多数

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

用长度为 $n$ 的二进制串 $s$ 表示服务器状态，$1$ 表示在线，$0$ 表示离线。

一次“电力传播”操作选择 $1\le i<j\le n$，要求 $s_i=s_j=1$，并且区间 $[i,j]$ 中在线服务器不少于离线服务器，即

若满足条件，就把区间 $[i,j]$ 的所有位置改为 $1$。

若一个二进制串能经过若干次（可以为零次）操作变成全 $1$ 串，则称它是“计分的”。求长度为 $n$ 的计分二进制串数量对 $m$ 取模的结果。

输入格式

一行包含两个整数 $n,m$。

输出格式

输出一个整数。

样例输入 1

2 100

样例输出 1

1

样例输入 2

3 10

样例输出 2

2

样例输入 3

4 3271890

样例输出 3

4

样例输入 4

17 123456

样例输出 4

32347

数据范围

$1\le n\le5000$，$10\le m\le10^9$。模数 $m$ 不保证为质数。