[BJ United Round #3] 三色树
题目描述
请你对满足以下要求的 $n$ 个节点的 **无标号无根树** 计数:
- 每个节点是三种颜色之一:红,蓝,黄
- 红色节点度数不超过 $4$,蓝色和黄色节点度数均不超过 $3$
- 黄色节点不能相邻
注意 **无标号无根树** 的意义是:如果两颗树可以通过重新编号的方法使得对应点颜色相同,对应连边一致,则认为是同一颗树。
答案对输入的质数 $p$ 取模。
输入输出格式
输入格式
两个正整数 $n,p$,意义如题面所示。
输出格式
一个整数,表示方案数对 $p$ 取模的结果。
输入输出样例
输入样例 #1
2 998244353
输出样例 #1
5
输入样例 #2
3 998244353
输出样例 #2
15
输入样例 #3
20 998244353
输出样例 #3
578067492
说明
![](https://i.niupic.com/images/2019/09/08/_51.png)
对于 $100\%$ 的数据,保证:
$1\le n \le 3000$
$9\times 10^8 \le p \le 1.01 \times 10^9$
保证 $p$ 为质数
By:EntropyIncreaser