题目描述

请你对满足以下要求的 $n$ 个节点的 无标号无根树 计数：

• 每个节点是三种颜色之一：红，蓝，黄
• 红色节点度数不超过 $4$，蓝色和黄色节点度数均不超过 $3$
• 黄色节点不能相邻

注意 无标号无根树 的意义是：如果两颗树可以通过重新编号的方法使得对应点颜色相同，对应连边一致，则认为是同一颗树。

答案对输入的质数 $p$ 取模。

输入格式

两个正整数 $n,p$，意义如题面所示。

输出格式

一个整数，表示方案数对 $p$ 取模的结果。

2 998244353

5

3 998244353

15

20 998244353

578067492

提示

对于 $100\%$ 的数据，保证：
$1\le n \le 3000$
$9\times 10^8 \le p \le 1.01 \times 10^9$
保证 $p$ 为质数

By：EntropyIncreaser