education-enumeration

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

SAMPLE INPUT
2 2

SAMPLE OUTPUT
14

Explanation

Call the grades A and B. Let A1,A2 be the students from grade A, and B1,B2 be the students from B. In the following notation, brackets denote a classroom.  The fourteen distinct ways are as follows: 
{A1},{B1},{A2},{B2}
{A1},{B2},{A2},{B1}
{A2},{B1},{A1},{B2}
{A2},{B2},{A1},{B1}
{B1},{A1},{B2},{A2}
{B1},{A2},{B2},{A1}
{B2},{A1},{B1},{A2}
{B2},{A2},{B1},{A1}
{A1},{B1,B2},{A2}
{A2},{B1,B2},{A1}
{B1},{A1,A2},{B2}
{B2},{A1,A2},{B1}
{A1,A2},{B1,B2}
{B1,B2},{A1,A2}

The following arrangements are either invalid, or equivalent to one of the ways above:
{A2,A1},{B1,B2} : This is equivalent to {A1,A2},{B1,B2}, since the order of students within a classroom doesn't matter 
{A1},{A2},{B1,B2} : This is illegal because the first two classrooms are adjacent and both belong to grade A.
{A1,B1},{A2},{B2} : This is illegal because the first classroom has a student from A and B.
{A1},{B1,B2},{},{A2} : This is illegal because the third classroom is empty.

Source: hackerearth | Difficulty: HARD
Tags: Polynomials and generating functions

Dynamic programming

Mathematics


Solutions: