Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3553
Hypercube

Time Limit: 5 Seconds      Memory Limit: 32768 KB

A N-dimension hypercube. m kinds of color.
Coloring each vertex, repeating is legal.
Please calculate the total number of different schemes. (if scheme A can be transformed into scheme B through any rotating or flipping, they are considered as the same scheme)
The answer may be too large, so please output the total number of different schemes mod 97654321.

Input

The input consists of several cases. Each case consists of two positive integers N and m (2 ≤ n ≤ 6, m ≤ 100000).

Output

For each case, output the total number of different schemes mod 97654321.

Sample Input

2 2

Sample Output

6

hint

a cube in 3-dimension

a hypercube in 4-dimension

a hypercube in 5-dimension


Author: WU, Yingxin
Contest: ZOJ Monthly, October 2011
Submit    Status