It's that time of the year, Felicity is around the corner and you can see people celebrating all around the Himalayan region. The Himalayan region has n gyms. The i-th gym has gi Pokemon in it. There are m distinct Pokemon types in the Himalayan region numbered from 1 to m. There is a special evolution camp set up in the fest which claims to evolve any Pokemon. The type of a Pokemon could change after evolving, subject to the constraint that if two Pokemon have the same type before evolving, they will have the same type after evolving. Also, if two Pokemon have different types before evolving, they will have different types after evolving. It is also possible that a Pokemon has the same type before and after evolving. 

Formally, an evolution plan is a permutation f of {1, 2, ..., m}, such that f(x) = y means that a Pokemon of type x evolves into a Pokemon of type y.

The gym leaders are intrigued by the special evolution camp and all of them plan to evolve their Pokemons. The protocol of the mountain states that in each gym, for every type of Pokemon, the number of Pokemon of that type before evolving any Pokemon should be equal the number of Pokemon of that type after evolving all the Pokemons according to the evolution plan. They now want to find out how many distinct evolution plans exist which satisfy the protocol.

Two evolution plans f1 and f2 are distinct, if they have at least one Pokemon type evolving into a different Pokemon type in the two plans, i. e. there exists an i such that f1(i) ≠ f2(i).

Your task is to find how many distinct evolution plans are possible such that if all Pokemon in all the gyms are evolved, the number of Pokemon of each type in each of the gyms remains the same. As the answer can be large, output it modulo 109 + 7.

Input

The first line contains two integers n and m (1 ≤ n ≤ 105, 1 ≤ m ≤ 106) — the number of gyms and the number of Pokemon types.

The next n lines contain the description of Pokemons in the gyms. The i-th of these lines begins with the integer gi (1 ≤ gi ≤ 105) — the number of Pokemon in the i-th gym. After that gi integers follow, denoting types of the Pokemons in the i-th gym. Each of these integers is between 1 and m.

The total number of Pokemons (the sum of all gi) does not exceed 5·105.

Output

Output the number of valid evolution plans modulo 109 + 7.

Examples

Input

2 3
2 1 2
2 2 3


Output

1


Input

1 3
3 1 2 3


Output

6


Input

2 4
2 1 2
3 2 3 4


Output

2


Input

2 2
3 2 2 1
2 1 2


Output

1


Input

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


Output

24

Note

In the first case, the only possible evolution plan is: 

<image>

In the second case, any permutation of (1, 2, 3) is valid.

In the third case, there are two possible plans: 

<image> <image>

In the fourth case, the only possible evolution plan is: 

<image>
 import java.util.*; 
        import java.math.*;
        import java.io.*;
        import java.text.DecimalFormat;
        import java.math.BigInteger;
        public class Main{
            //static int d=20;
            static long mod=1000000007 ;
            static HashMap<String,Double> hm=new HashMap<>(); 
            static ArrayList<ArrayList<Integer>> arr;
            static long[] dp1,dp2;
            static int[] a;
            static int[] vis,num;
            static long max;
            static int id;
            public static void main(String[] args)  throws IOException {
                boolean online =false;
                String fileName = "C-large-practice";
                PrintWriter out; 
                if (online) {
                    s.init(new FileInputStream(new File(fileName + ".in")));
                     out= new PrintWriter(new FileWriter(fileName + "out.txt"));
                }
                 else {
                    s.init(System.in);   
                
                    out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
                }
                int n=s.ni();
                int m=s.ni();
                long[] powers = new long[n];
                powers[0] = 1;
                long PRIME = 47;
                long MODULO = 12480793571231L;
                for (int i = 1; i < n; ++i) {
                    powers[i] = (powers[i - 1] * PRIME) % MODULO;
                }
                
                long[] pre=new long[m+1];
                int[] cur=new int[m+1];
                for(int i=0;i<n;i++){
                    int num=s.ni();
                    
                    int[] z=new int[num];
                    //HashMap<Integer,HashSet<Integer>> hm=new HashMap<>();
                    for(int j=0;j<num;j++){
                        int x=s.ni();
                        z[j]=x;
                        cur[x]++;
                    }
                    HashSet<Integer> hs=new HashSet<>();
                    for(int j=0;j<num;j++){
                        if(!hs.contains(z[j])){
                            hs.add(z[j]);
                            pre[z[j]]=(pre[z[j]]+(powers[i]*cur[z[j]])%MODULO)%MODULO;

                        }

                        
                    }
                   


                }

                long ans=1;
                HashMap<Long,Integer> hm2=new HashMap<>();
                for(int i=1;i<=m;i++ ){

                    if(!hm2.containsKey(pre[i])){
                        hm2.put(pre[i],1);
                    }
                    else{
                        hm2.put(pre[i],hm2.get(pre[i])+1);
                    }
                }
                long[] fac=new long[1000001];
                fac[0]=1L;
                for(int i=1;i<=1000000;i++){
                    fac[i]=(fac[i-1]*i)%mod;
                }
               // System.out.println(hm2.keySet());
                for(Long q:hm2.keySet()){
                    ans=(ans*fac[hm2.get(q)])%mod;
                }
                out.println(ans);
                out.close();
 
            }
            public static boolean check(long x){
                if(x%4==0 || x%7==0 || x%11==0)
                    return true;
                if(x<4 || x<7 || x<11)
                    return false;
                if(x%2==0){
                    return check(x/2);
                }
                else
                    return check(x/2) && check((x+1)/2);
            }
            public static int angle(int x1,int x2,int x3,int y1,int y2,int y3){
                long val=(y2-y1)*1L*(x3-x2)-(y3-y2)*1L*(x2-x1);
                if(val<0)
                    return 1;
                else if(val>0)
                    return -1;
                else
                    return 0;
            }
            
            static class BIT{
            
                int N;
                int tree[];
                
                BIT(int N){
                    this.N = N;
                    tree = new int[N + 1];
                }
                
                void update(int idx){
                    while(idx <= N){
                        tree[idx]++;
                        idx += (idx & -idx);
                    }
                }
                
                int query(int l,int r){
                    if(l == 1)
                        return read(r);
                    else
                        return read(r) - read(l-1);
                }
                
                int read(int idx){
                    int sum = 0;
                    while(idx > 0){
                        sum += tree[idx];
                        idx -= (idx & -idx);
                    }
                    return sum;
                }
            }
            public static boolean pal(String a){
                int i=0;
                int j=a.length()-1;
                while(i<j){
                    if(a.charAt(i)!=a.charAt(j)){
                        return false;
                    }
                    i++;
                    j--;
                }
                return true;
                    
            }
            public static long find(long n,long k){
                if(n==2){
                    if(k==1 || k==3)
                        return 1;
                    else
                        return 2;
                }
                long t=pow2(2,n,mod)-1;
                long z=(t+1)/2;
                if(k==z)
                    return n;
                if(k<z)
                    return find(n-1,k);
                else
                    return find(n-1,k-z);
            }
            public static long pow2(long a,long b,long mod){
                    long ans=1;
                    while(b>0){
                        if(b%2==1)
                            ans=(a*ans)%mod;
                        a=(a*a)%mod;
                        b/=2;
                    }
                    return  ans;
            }
            public static double pow3(double a,long b){
                    double ans=1;
                    while(b>0){
                        if(b%2==1)
                            ans=(a*ans);
                        a=(a*a);
                        b/=2;
                    }
                    return  ans;
            }
 
             static class name implements Comparable<name> {
                long l,b,h;
                public name(long   x,long y,long z){
                    {
                        l=x;
                        b=y;
                    }
                    
                    
                    h=z;
                }
                public int compareTo(name o){
                    return -(int)(l*b-o.l*o.b);
                }
                
            }
            public static class s {
                static BufferedReader reader;
                static StringTokenizer tokenizer;
            
                /** call this method to initialize reader for InputStream */
                static void init(InputStream input) {
                    reader = new BufferedReader(
                                new InputStreamReader(input) );
                    tokenizer = new StringTokenizer("");
                }   
            
                /** get next word */
                static String ns() throws IOException {
                    while ( ! tokenizer.hasMoreTokens() ) {
                        //TODO add check for eof if necessary
                        tokenizer = new StringTokenizer(
                            reader.readLine() );
                    }
                    return tokenizer.nextToken();
                }
            
                static int ni() throws IOException {
                    return Integer.parseInt( ns() );
                }
            
                static double nd() throws IOException {
                    return Double.parseDouble( ns() );
                }
                static long nl() throws IOException {
                    return Long.parseLong( ns() );
                }
            }
        }
                
