Problem Description

Count the number of unlabeled unrooted trees with \( n \) nodes that satisfy the following requirements:

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

Note that unlabeled unrooted trees mean that if two trees can be made identical by reassigning their node numbers while keeping the same colors and connections, they are considered the same tree.

The answer should be taken modulo \( p \).

Input Format

Two positive integers \( n \) and \( p \), as described in the problem statement.

Output Format

An integer representing the number of valid trees modulo \( p \).

Sample Input and Output

Sample Input #1

2 998244353

Sample Output #1

5

Sample Input #2

3 998244353

Sample Output #2

15

Sample Input #3

20 998244353

Sample Output #3

578067492

Notes

For \( 100\% \) of the data, it is guaranteed that:

• \( 1 \le n \le 3000 \)
• \( 9 \times 10^8 \le p \le 1.01 \times 10^9 \)
• \( p \) is a prime number

By: EntropyIncreaser

见题面 Input 部分

见题面 Output 部分