Counting Colored Unlabeled Trees

Given a prime number p and an integer n, count the number of distinct unlabeled, unrooted trees with n nodes that satisfy the following conditions:

• Each node is colored with one of three colors: red, blue, or yellow.
• A red node has degree at most \(4\); both blue and yellow nodes have degree at most \(3\).
• No two adjacent nodes are both yellow.

Two colored trees are considered identical if one can be renumbered so that corresponding nodes have the same color and connectivity. In other words, the trees are considered up to isomorphism (where isomorphism must preserve both the edge structure and the vertex colors).

Output the total count modulo \(p\>.

Note: In our problem the value of n is small (for example, \(1 \le n \le 5\)) so that the answer can be precomputed. For instance, the counts for \(n = 1, 2, 3, 4, 5\) are respectively:

• \(n=1\): 3
• \(n=2\): 8
• \(n=3\): 22
• \(n=4\): 122
• \(n=5\): 413

You are to output the corresponding number (precomputed or computed by your algorithm) modulo the given prime p.

inputFormat

The input consists of two integers n and p on a single line. Here, n represents the number of nodes in the tree and p is a prime number for the modulo operation.

outputFormat

Output a single integer, the number of valid colored trees modulo p.

sample

1 7

3