Problem C
How Many Teams?

Input: Standard Input

Output: Standard Output

 

University of Fixed Problems (UFP) was planning to host a national level computer programming competition but just before the event they have realized that they don’t have a budget that is big enough for a national programming contest!

On the eve of the contest, you get a phone call from them and hear the inevitable – “The Contest is Called Off”. However, they said they will be hosting a ‘General Knowledge’ competition instead.

The restriction on the number of teams goes like this:

Your university can send a total of N contestants with K members in each team. That means there are a total of N/K teams.

A notice was sent to all departments of your university asking them to select their best students for participating in this competition. Due to the limited number of seats, a department can send at most 3 members.

 

You managed to gather N students from various departments. Within this limited time, it’s not going to be viable to come up with the best balanced teams. So you tell all these students to line up randomly and assign first K students in one team, the next K students in another team and so on. But, one rule that you are going to follow is that two person from the same department cannot be in the same team. This will enable the teams to be more balanced.

 

Of the entire N! (N Factorial) permutations of lining up, can you find out how many of those are valid? A permutation is valid if you can assign the teams according to the rules mentioned above.

 

Example: Consider a case where N = 4 and K = 2.

 

PM-MATH, LT-CSE, DK-MATH, MMR-EEE

 

Suppose you have 4 students (PM, LT, DK and MMR) and their departments are (MATH, CSE, MATH and EEE) respectively. You have to form 2 teams with 2 members in each team.

 

Some valid permutations are: (PM LT DK MMR) (LT PM DK MMR) (MMR PM LT DK)
And some invalid permutations are: (PM DK MMR LT) (LT MMR DK PM).

 

Input

The first line is an integer T(T<500) that indicates the number of test cases. Each case starts with 2 integers N(1 <= N <= 100) and K(1 <= K <= 10). It is guaranteed that N % K = 0. The next line will contain N space separated strings of the format S1-D1 S2-D2 S3-D3 ... SN-DN. Si gives you the names of each student and Di gives you the corresponding department of that student. All the students’ names will be distinct. The department and student names will be alphanumeric and the length of each will be at most 20.

 

Output

For each case, output the case number followed by the total number of valid permutations. Since the result could be very big, output the result modulo 1234.

 

Sample Input                                     Output for Sample Input

3
2 2
sohelH-CSE samee-CSE
4 2
Blind-ECS sidky-CSE muntasir-CSC ShadowCoder-EEE
4 2

ABC-D1 DEF-D1 ghi-D2 jkl-D3

Case 1: 0
Case 2: 24
Case 3: 16

 

Problemsetter: Sohel Hafiz

Special Thanks to: Arifuzzaman Arif