Problem Description

Please count the number of unlabeled unrooted trees with $n$ nodes that satisfy the following requirements:

• Each node has one of three colors: red, blue, or yellow.
• The degree of a red node is at most $4$, and the degrees of blue and yellow nodes are both at most $3$.
• Yellow nodes cannot be adjacent.

Note that the meaning of an unlabeled unrooted tree is: if two trees can be made identical by renumbering the nodes so that the corresponding nodes have the same colors and the corresponding edges match, then they are considered the same tree.

The answer should be taken modulo the prime number $p$ given in the input.

Input Format

Two positive integers $n,p$, with the meanings as described above.

Output Format

One integer, representing the number of valid trees modulo $p$.

2 998244353

5

3 998244353

15

20 998244353

578067492

Hint

For $100\%$ of the testdata, it is guaranteed that: $1\le n \le 3000$. $9\times 10^8 \le p \le 1.01 \times 10^9$. It is guaranteed that $p$ is prime.

By: EntropyIncreaser

Translated by ChatGPT 5