Exponentiation with Partition Exponents

Given two integers n and m, let x be the number of essentially different graphs on n nodes in which each connected component is a complete graph. In other words, two graphs are considered the same if they are isomorphic. It turns out that each such graph is uniquely determined by the multiset of sizes of its connected components. Hence, x is exactly the number of partitions of n into positive integers.

You are to compute

\[ m^x \bmod P, \]

where the prime P is given by \(10^9-401\). All formulas must be in \(\LaTeX\) format.

inputFormat

The input consists of a single line containing two space-separated integers: n and m, where n is the number of nodes, and m is the base of the exponentiation.

outputFormat

Output a single integer representing \(m^x \bmod (10^9-401)\), where \(x\) is the number of partitions of \(n\) (the number of essentially different graphs described above).

sample

1 2

2