题目背景

在研究各种奇特的编程语言时，你设计出了一门名为 Brainstuck 的极简语言。

这门语言没有变量、数组和输入输出，只有一个可以存储任意大小整数的内存单元，以及四种指令：+、-、[、]。虽然语法看起来十分简单，但一个程序是否能够停止运行，却可能取决于多层循环之间复杂的相互作用。

现在，你想知道：长度恰好为 $N$ 的所有 Brainstuck 程序中，有多少个既满足括号匹配，又能在有限步内结束执行？

题目描述

一个 Brainstuck 程序是一个仅由以下四种字符组成的字符串：

+ - [ ]

解释器只有一个内存单元，该单元可以保存任意大小的整数。程序开始执行时：

• 内存单元的值为 $0$；
• 指令指针指向程序的第一个字符。

解释器依次执行指令。每条指令的含义如下：

• +：将内存单元的值增加 $1$；
• -：将内存单元的值减少 $1$；
• [：检查当前内存单元的值：
  • 若其值为 $0$，则将指令指针移动到与当前 [ 匹配的 ]；
  • 否则不进行跳转；
• ]：检查当前内存单元的值：
  • 若其值不为 $0$，则将指令指针移动到与当前 ] 匹配的 [；
  • 否则不进行跳转。

在每条指令执行完毕后，指令指针都会再向后移动一个字符。

当指令指针移动到程序末尾之后时，程序结束。

括号按照通常的嵌套方式匹配。形式化地，对于位置 $i$ 上的一个 [，与它匹配的 ] 位于最小的位置 $j>i$，满足子串 $[i,j]$ 中 [ 与 ] 的数量相等。

一个 Brainstuck 程序被称为 合法程序，当且仅当它同时满足：

1. 所有 [ 和 ] 均正确匹配；
2. 程序从初始状态开始执行后，会在有限步内结束。

给定整数 $N$ 和模数 $M$，请计算长度恰好为 $N$ 的合法 Brainstuck 程序数量，并对 $M$ 取模。

输入格式

一行两个整数 $N,M$。

输出格式

输出一个整数，表示长度恰好为 $N$ 的合法 Brainstuck 程序数量对 $M$ 取模后的结果。

样例 1

输入

2 1000000000

输出

5

说明

五个合法程序分别为：

++
-+
+-
--
[]

程序 [] 只执行一步：初始值为 $0$，执行 [ 时直接跳到对应的 ]，随后指令指针继续右移并离开程序。

样例 2

输入

3 1000000000

输出

12

样例 3

输入

5 1000000000

输出

92

样例 4

输入

16 1000000000

输出

55450070

样例 5

输入

13 163

输出

64

数据范围

对于所有数据：

$$1\le N\le 100,$$ $$2\le M\le 10^9.$$