Mr X, not so good in maths, was trying to solve a problem . It was his homework assignment , so he had to solve the problem in any circumstance. He is unable to solve the problem and therefore asks for your help.
There is a 2D matrix of size N*M containing the numbers from 0 to N-1. You have to find the number of ways in which if one number is chosen from each row, the union of all chosen numbers will be {0,1,2,......N-1}. As the number of ways can be very large, output the answer mod 109+7.
CONSTRAINTS
\(1 \le N \le 20\) (N: number of rows)
\(1 \le M \le 10^6\) (M: number of columns)
Each number of the matrix is between 0 and N-1 (Both inclusive)
INPUT
First line contains 2 integers N and M.
In next N lines, each line contain M space-separated integers.
OUTPUT
Output a single integer denoting the answer to the above problem.