0

Hat Combination

Difficulty: HARD
Contributed By
Ankush Gupta
Avg. time to solve
50 min
Success Rate
60%

Problem Statement

It is the birthday of the Ultimate Ninja Ankush, and his fellow Seito’s have decided to organize a party in the dojo. The Ultimate Ninja Ankush loves a party and brings hats for everyone, but the students are very choosy and prefer only some hats. Since Ankush is the Ultimate ninja, he loves a brain teaser. He wants to know the total Number of Combinations such that all students wear different hats.

There are ‘N’ students, and Ultimate Ninja Ankush has exactly 40 varieties of hats numbered from, each of the ‘N’ students have ‘M’ preference of hats out of the 40, and we want to know the total number of Combination such that all students wear different hats.

More Formally, There are n people and 40 types of hats labeled from 1 to 40.

Given a list of integers hats, where ‘hats[i]’ is a list of all hats preferred by the i-th person. Return the number of ways that the ‘N’ students wear different hats to each other. Since the answer may be too large, return it modulo 10 ^ 9 + 7.

For example:

Given:
‘N’ = 2, ‘M’ = 3.
‘Hats’ = [[1, 2, 3],
          [3, 4, 5]]

The answer will be 8, the combinations can be (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5).
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘N,’ where ‘N’ is the number of rows in ‘HATS’ and ‘M’ where ‘M’ is the number of columns in ‘HATS’.

The next ‘N’ line of each test case contains ‘M’ space-separated integers, which tell the preference of hats of the ‘i’ the student.
Output Format :
For each test case, return the number of ways that the ‘N’ students wear different hats to each other. Since the answer may be too large, return it modulo 10 ^ 9 + 7.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10
1 <= ‘M’ <= 40
1 <= ‘HATS[i][j]’ <= 40

Time Limit: 1 sec.

Sample Input 1 :

2
2 3
1 2 3
3 4 5
3 3
1 2 3
1 2 4
1 2 5

Sample Output 1 :

8
13  

Explanation of the Sample Input 1:

In the first test case, The answer will be 8. The combinations can be (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5).

In the second test case, The answer will be 13, the combinations can be (1,2,5),(1,4,5), (1,4,2), (2,1,5), (2,4,5),(2,4,1), (3,1,2), (3,1,5), (3,2,5), (3,2,1),(3,4,1), (3,4,2), (3,4,5).

Sample Input 2 :

2
4 4
1 2 3 4
1 2 3 4 
1 2 3 4
1 2 3 4
3 2
1 2
3 4
5 6
3 3

Sample Output 2 :

24
8
Reset Code
Full screen
copy-code
Console