8353번 - Cliquers 다국어

문제

An undirected graph is called a cliquer if each connected component of the graph is a clique. Maurycy has drawn all cliquers with n vertices on a piece of paper and is going to assess beauty of each of them with a number from the set {1, ..., m} (in particular, different cliquers may be assigned equal grades). In how many ways can he do this? The result should be computed modulo 10⁹ - 401. The figure below depicts all cliquers for n = 3.

입력

The only line of the standard input contains two integers n and m (1 ≤ n, m ≤ 200 000), separated by a single space and denoting the number of vertices of each cliquer and the number of grades respectively.

출력

The only line of the standard output should contain the number of possible sets of grades modulo 10⁹ - 401.

제한

힌트