Symmetric Labeled Cliquer Coloring

We define an undirected graph on \(n\) vertices (with vertices labeled from 1 to \(n\)) as a symmetric labeled cliquer if and only if every connected subgraph has the same number of vertices and is a complete graph (i.e. every pair of vertices in the subgraph is adjacent).

It can be proven that the only graph satisfying this condition is the edgeless graph, because if there were any edge the graph would have a connected subgraph with 2 vertices as well as the trivial 1-vertex subgraph. Hence, for any \(n \ge 1\), there is exactly one symmetric labeled cliquer.

Now, given \(m\) colors and all symmetric labeled cliquers on \(n\) vertices, we color each symmetric labeled cliquer with one color. (Note that different symmetric labeled cliquers may be colored with the same color.)

The task is to determine the number of ways to color the graphs modulo \(10^9-401\).

inputFormat

The input consists of two space-separated integers \(n\) and \(m\).

• \(1 \le n \le 10^9\)
• \(1 \le m \le 10^9\)

outputFormat

Output a single integer representing the number of ways to color all symmetric labeled cliquers modulo \(10^9-401\).

sample

1 7

7