0

# Hat Combination

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

Problem Statement

#### 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
``````
Console