Trees with an odd number of independent sets

You are given a natural number (n) (where (n $\le$ 1000)) and a prime number (p) (such that (10^7 < p < 10^9)). Your task is to determine the number of rooted trees with unmarked vertices that have an odd number of independent sets. You should output the result modulo (p).

A tree is considered rooted with unmarked vertices if one of its vertices is designated as the root, and the sequence of children for any vertex does not matter. In other words, two trees are identical if they can be made to match by reordering the non-root vertices. Formally, two rooted trees with unmarked vertices, (T_1) and (T_2), are equal if there exists a bijective function (f) from the vertex set of (T_1) to the vertex set of (T_2), which maps the root of (T_1) to the root of (T_2), and for every edge ((u, v)) in (T_1), there is a corresponding edge ((f(u), f(v))) in (T_2).

An independent set in a graph is a set of vertices (which may be empty) such that no two vertices in the set are adjacent.

Input

The input consists of a single line containing the numbers (n) and (p).

Output

Output the solution to the problem on a single line.

Examples