考虑一个非负整数序列 $\langle a_1, a_2, \dots, a_n \rangle$。序列中的一个上升（ascent）是指一对相邻元素，其中索引较大的元素值较大。例如，序列 $\langle 0, 2, 3, 1, 0 \rangle$ 中有两个上升：从 $a_1 = 0$ 到 $a_2 = 2$，以及从 $a_2 = 2$ 到 $a_3 = 3$。记 $A_k$ 为序列前 $k$ 个元素中的上升数量。在上述例子中，$A_1 = 0, A_2 = 1, A_3 = 2, A_4 = 2, A_5 = 2$。

如果一个序列满足 $a_1 = 0$ 且对于每个 $i \ge 2$ 都满足不等式 $a_i \le A_{i-1} + 1$，则称该序列为上升序列。例如，序列 $\langle 0, 2, 3, 1, 0 \rangle$ 不是上升序列，因为 $a_2 = 2$ 而 $A_1 = 0$。而序列 $\langle 0, 1, 0, 2, 3 \rangle$ 是一个上升序列，因为 $A_1 = 0, A_2 = 1, A_3 = 1, A_4 = 2$。

如果非负整数序列 $\langle a_1, a_2, \dots, a_n \rangle$ 不存在索引 $i, j, k$ 满足 $i < j < k$ 且 $a_j < a_k < a_i$，则称该序列避开了模式 201。例如，序列 $\langle 0, 1, 0, 2, 3 \rangle$ 避开了模式 201，而 $\langle 0, 1, 2, 3, 1, 0, 2 \rangle$ 没有避开模式 201，因为对于 $i = 4, j = 6, k = 7$，有 $a_j = 0 < a_k = 2 < a_i = 3$。

给定两个整数 $n$ 和 $p$。求长度为 $n$ 且避开模式 201 的上升序列的数量，并将结果对 $p$ 取模。

输入格式

输入仅一行，包含两个整数 $n$ 和 $p$ ($1 \le n \le 500; 2 \le p \le 10^9 + 123; p$ 为质数)。

输出格式

输出一个整数——长度为 $n$ 且避开模式 201 的上升序列的数量，对 $p$ 取模。

样例

输入格式 1

3 23

输出格式 1

5

说明

在第一个样例测试中，有 5 个长度为 3 且避开模式 201 的上升序列：$\langle 0, 0, 0 \rangle, \langle 0, 0, 1 \rangle, \langle 0, 1, 0 \rangle, \langle 0, 1, 1 \rangle, \langle 0, 1, 2 \rangle$。

输入格式 2

5 239

输出格式 2

52

说明

在第二个样例测试中，共有 53 个长度为 5 的上升序列，其中除了 $\langle 0, 1, 2, 0, 1 \rangle$ 外，其余均避开了模式 201。