See Russian Translator

Elaine is in charge of assigning classrooms for her new school. She has n different grades, each with k distinct students in each grade. Thus, Elaine has a total of n × k distinct students.

Elaine wants to arrange the classrooms in a line. She does this as follows.

• First, she chooses the number of rooms and assigns each room to a different grade. No two adjacent rooms can belong to the same grade.
• She will assign each student to a classroom. A student can only go in a classroom if it is the same grade as him or her. Each classroom must have at least one student.

Elaine wonders how many different arrangements she can create. Two arrangements are different if one of the conditions holds:

• The number of rooms is different.
• Some room is assigned to a different grade in the two arrangements
• Some student is assigned to a different room in the two arrangements

Help Elaine count the number of valid arrangements. Print this number modulo 167772161.

Input format:

The first and only line of input will contain two integers n,k.

Output format:

The output will be just one line, representing the number of ways modulo 167772161.

Constraints:

18 pts:
1 ≤ n ≤ 3
1 ≤ k ≤ 3

25 pts:
1 ≤ n ≤ 10,000
1 ≤ k ≤ 2

40 pts:
1 ≤ n ≤ 50
1 ≤ k ≤ 50

17 pts:
1 ≤ n ≤ 10,000
1 ≤ k ≤ 50