TSHIRTS ( CodeChef )

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
using namespace std;
#define mod 1000000007
int bitcount(int value);
int getno(string str, int start, int end)
{
        int val =0;
        for(int i=start;i<=end;i++)
        {
                val = val*10 + (int)(str[i]-48);
        }
        return val;
}
long long int bitmask(int A[10][101], int size)
{
        int val = 1 << size;
        long long int dp[1<<size][101];
        for(int i=0;i<val;i++)
        {
                for(int j=0;j<101;j++)
                {
                        dp[i][j] = 0;
                }
        }
        for(int i=0;i<val;i++)
        {
            int mask = i;
            int setbits = bitcount(mask);
            for(int j=0;j<=100;j++)
            {
                for(int k=0;k<size;k++)
                {
                    if((mask&(1<<k))!=0 && A[k][j]==1)
                    {
                        if(j!=0)
                        {
                                if(setbits == 1)
                                        dp[mask][j] = 1;
                                else
                                    dp[mask][j] = (dp[mask][j] + dp[mask ^ (1<<k)][j-1])%mod;
                            //cout << mask << " " << j << " ::::"<< endl;
                        }
                        else
                        {
                                if(setbits == 1)
                                    dp[mask][j] = 1;
                                else
                                        dp[mask][j] = 0;
                            //cout << mask << " " << j << " ::"<< endl;
                        }
                    }
                }
                if(j!=0)
                dp[mask][j] = (dp[mask][j] + dp[mask][j-1])%mod;
            }
        }
        return dp[val-1][100];
}
int bitcount(int value)
{
        int count =0;
        long v1 = value;
        while(v1!=0)
        {
            if(v1%2==1)
            {
                count++;
            }
            v1 = v1/2;
        }
        return count;
}
int main()
{
        int t;
        cin >> t;
        while(t--)
        {
                int n;
                cin >> n;
            int ent[10]={0};
            int A[10][101];
            for(int i=0;i<10;i++)
            {
                for(int j=0;j<101;j++)
                {
                    A[i][j] = 0;
                }
            }
            for(int i=0;i<n;i++)
            {
                        string line;
                        //cin >> line;
                        getline(cin, line);
                        if(line == "")
                        {
                                i--;
                                continue;
                        }
                        int len=0;
                        int start=0;
                        int size =0;
                        while(line[len] != '\0')
                        {
                                len++;
                                if(line[len] == ' ')
                                {
                                        int no = getno(line,start,len-1);
                                        A[i][no] = 1;
                                        start = len+1;
                                        size++;
                                        //cout << no << " ";
                                }
                        }
                        int val = getno(line,start,len-1);
                        size++;
                       // cout << val << endl;
                        A[i][val] = 1;
            }
            long long int ans = bitmask(A,n);
                cout << ans << endl;
        }
}