Enumeration of Good Graphs (Unlabeled Cographs)

A simple undirected graph on n vertices is defined as good if it satisfies the following conditions:

• A single vertex is good.
• If several good graphs are taken as the connected components, then the resulting graph is good.
• The complement of a good graph is good.

Two good graphs are considered essentially different if and only if no relabeling of vertices makes them isomorphic. It can be shown that the class of good graphs is exactly the class of cographs (complement-reducible graphs). The known sequence for the number of unlabeled cographs (also known as good graphs) for n = 1,2,3,... is:

\[ 1, \; 2, \; 4, \; 10, \; 26, \; 76, \; 232, \; 764, \; 2620, \; 9496, \dots \]

Given a positive integer \( n \) and a prime modulus \( P \), compute the number of essentially different good graphs on \( n \) vertices modulo \( P \). For the purpose of this problem, you may assume that \( n \) is small (for example, \( n \le 10 \)), so that the answer is one of the above values modulo \( P \).

inputFormat

The input consists of a single line containing two space‐separated integers: n and P.

• n is the number of vertices.
• P is a prime number used as the modulus.

outputFormat

Output a single integer: the number of essentially different good graphs on n vertices taken modulo P.

sample

1 1000

1