Read problems statements in Mandarin Chinese  and Russian. 

Little Elephant and his friends are going to a party. Each person has his own collection of T-Shirts. There are 100 different kind of T-Shirts. Each T-Shirt has a unique id between 1 and 100. No person has two T-Shirts of the same ID.
They want to know how many arrangements are there in which no two persons wear same T-Shirt. One arrangement is considered different from another arrangement if there is at least one person wearing a different kind of T-Shirt in another arrangement.

------ Input ------ 

First line of the input contains a single integer  T  denoting number of test cases. Then T test cases follow.
For each test case, first line contains an integer N, denoting the total number of persons. Each of the next N lines contains at least 1 and at most 100 space separated distinct integers, denoting the ID's of the T-Shirts i^{th} person has.

------ Output ------ 

For each test case, print in single line the required number of ways modulo 1000000007 = 10^{9}+7.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10$

------ Example ------ 

Input:
2
2
3 5
8 100
3
5 100 1
2
5 100

Output:
4
4

------ Explanation ------ 

For the first case, 4 possible ways are (3,8), (3,100), (5,8) and (5,100).For the second case, 4 possible ways are (5,2,100), (100,2,5), (1,2,100), and (1,2,5).

Difficulty: HARD
Tags: Dynamic programming

Bit manipulation

Mathematics
Skill types: Dynamic programming

Bit manipulation

Starter code:

Solutions:
import sys
sys.setrecursionlimit(1000000)
(t, mod) = (int(sys.stdin.readline()), 1000000007)
while t:
	n = int(sys.stdin.readline())
	a = [[0 for _ in range(101)] for _ in range(n + 1)]
	for i in range(n):
		cur = [int(x) for x in sys.stdin.readline().split()]
		for x in cur:
			a[i][x] = 1
	t -= 1
	lim = 1 << n
	dp = [[-1 for _ in range(lim + 1)] for _ in range(101)]

	def tshirt(shirt, mask):
		if mask == lim - 1:
			return 1
		if shirt > 100:
			return 0
		if dp[shirt][mask] != -1:
			return dp[shirt][mask]
		ans = 0
		for ppl in range(n):
			chk = 1 << ppl
			if chk & mask:
				continue
			if not a[ppl][shirt]:
				continue
			ans += tshirt(shirt + 1, chk | mask) % mod
		ans += tshirt(shirt + 1, mask) % mod
		dp[shirt][mask] = ans
		return ans
	print(tshirt(0, 0))


md = 10 ** 9 + 7
book = dict()
ids = [set()] * 10
n = 0

def poss(i, a):
	if (i, tuple(a)) in book.keys():
		return book[i, tuple(a)]
	elif i == 101:
		if all(a):
			return 1
		else:
			return 0
	else:
		res = poss(i + 1, a)
		for j in range(n):
			if i in ids[j] and (not a[j]):
				b = a.copy()
				b[j] = True
				res = (res + poss(i + 1, b)) % md
		book[i, tuple(a)] = res
		return res
for _ in range(int(input())):
	N = int(input())
	n = N
	idlst = []
	for k in range(N):
		e = set(list(map(int, input().split())))
		idlst.append(e)
	ids = idlst
	print(poss(1, [False] * N) % md)
	book.clear()


mod = 1000000000.0 + 7
import numpy as np
t = int(input())
for _ in range(t):
	n = int(input())
	ingr = [0] * 101
	for i in range(n):
		for shirt in map(int, input().split(' ')):
			ingr[shirt] |= 1 << i
	dp = [[0 for _ in range((1 << n) + 1)] for _ in range(101)]
	dp[0][0] = 1
	for i in range(1, 101):
		for mask in range(1 << n):
			dp[i][mask] += int(dp[i - 1][mask])
			dp[i][mask] %= mod
			tmask = mask
			while tmask != 0:
				bit = tmask & -tmask
				if bit & ingr[i]:
					dp[i][mask] += int(dp[i - 1][mask ^ bit])
					dp[i][mask] %= mod
				tmask -= bit
	print(int(dp[100][(1 << n) - 1]))


import sys
sys.setrecursionlimit(10 ** 6)
ip = sys.stdin.readline
op = sys.stdout.write

def recursive_thinking(shirts, n, t_id, mask, tb):
	if mask == 2 ** n - 1:
		return 1
	if t_id == 101:
		return 0
	if (t_id, mask) in tb:
		return tb[t_id, mask]
	ways = recursive_thinking(shirts, n, t_id + 1, mask, tb)
	for j in range(n):
		if mask & 1 << j == 0 and t_id in shirts[j]:
			ways += recursive_thinking(shirts, n, t_id + 1, mask | 1 << j, tb)
	tb[t_id, mask] = ways
	return ways
t = int(ip())
res = []
mod = 1000000007
for _ in range(t):
	n = int(ip())
	shirts = {}
	for i in range(n):
		lst = [int(x) for x in ip().split()]
		shirts[i] = set(lst)
	ways = recursive_thinking(shirts, n, 1, 0, {})
	res.append(ways % mod)
for val in res:
	op(str(val) + '\n')


mod = 1000000007

def solve(shirt, people, dp, mask, n):
	if mask == 0:
		return 1
	if shirt > 100:
		return 0
	if dp[shirt][mask] != -1:
		return dp[shirt][mask]
	ans = 0
	for i in range(1, n + 1):
		if mask & 1 << i - 1 != 0 and people[i][shirt]:
			ans = ans + solve(shirt + 1, people, dp, mask ^ 1 << i - 1, n) % mod
	ans = (ans + solve(shirt + 1, people, dp, mask, n)) % mod
	dp[shirt][mask] = ans
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	people = []
	dp = []
	for i in range(101):
		dp.append([-1 for j in range(1025)])
	for i in range(11):
		people.append([False for j in range(101)])
	for i in range(1, n + 1):
		temp = list(map(int, input().split()))
		for x in temp:
			people[i][x] = True
	print(solve(1, people, dp, (1 << n) - 1, n))


from functools import lru_cache
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	mapping = []
	for i in range(n):
		tshirts = {int(tshirt) for tshirt in input().split()}
		mapping.append(tshirts)

	@lru_cache(maxsize=None)
	def comp(mask, tshirt):
		if tshirt == 101:
			if mask == 0:
				return 1
			else:
				return 0
		ans = comp(mask, tshirt + 1) % mod
		for i in range(n):
			if mask & 1 << i:
				if tshirt in mapping[i]:
					ans += comp(mask ^ 1 << i, tshirt + 1)
					ans %= mod
		return ans
	print(comp(2 ** n - 1, 1))


from collections import defaultdict
mod = 10 ** 9 + 7

def solve(shirt, mask, N):
	if mask == (1 << N) - 1:
		return 1
	if shirt > 100:
		return 0
	if dp[shirt][mask] != -1:
		return dp[shirt][mask]
	ans = 0
	for i in range(1, N + 1):
		if mask & 1 << i - 1 != 0:
			continue
		if people[i][shirt] == 1:
			ans += solve(shirt + 1, mask | 1 << i - 1, N)
			ans %= mod
	ans += solve(shirt + 1, mask, N)
	ans %= mod
	dp[shirt][mask] = ans
	return ans
for t in range(int(input())):
	N = int(input())
	people = [[-1] * 101 for i in range(11)]
	dp = [[-1] * 1025 for i in range(101)]
	for j in range(N):
		lst = list(map(int, input().split()))
		for k in lst:
			people[j + 1][k] = 1
	print(solve(1, 0, N))


MOD = 1000000007

def findAns(mask, tid, n, people, dp):
	if mask == (1 << n) - 1:
		return 1
	if tid >= 101:
		return 0
	if dp[tid][mask] != -1:
		return dp[tid][mask]
	ans = findAns(mask, tid + 1, n, people, dp)
	for i in range(n):
		if mask & 1 << i:
			continue
		if tid in people[i]:
			ans += findAns(mask | 1 << i, tid + 1, n, people, dp)
			ans %= MOD
	dp[tid][mask] = ans
	return dp[tid][mask] % MOD
for _ in range(int(input())):
	n = int(input())
	people = []
	dp = [[-1 for i in range(1 << n)] for j in range(101)]
	for j in range(n):
		arr = [int(c) for c in input().split()]
		s = set(arr)
		people.append(s)
	print(findAns(0, 1, n, people, dp) % MOD)


for _ in range(int(input())):
	n = int(input())
	arr = [[] for j in range(100)]
	memo = {}
	for i in range(n):
		for j in input().split():
			arr[int(j) - 1].append(i)
	arr = [i for i in arr if i]

	def helper(index, mask):
		if index == len(arr):
			return 1 if not mask else 0
		if not mask:
			return 1
		if (index, mask) in memo:
			return memo[index, mask]
		count = 0
		for i in arr[index]:
			if mask & 1 << i:
				count += helper(index + 1, mask ^ 1 << i)
		count += helper(index + 1, mask)
		memo[index, mask] = count % 1000000007
		return memo[index, mask]
	print(helper(0, (1 << n) - 1) % 1000000007)


MAX_T_SHIRT = 100
t_shirts_elephant_map = []
dp = []

def find(mask, t_shirt_id):
	if mask == 0:
		return 1
	if t_shirt_id < 0:
		return 0
	if dp[mask][t_shirt_id] != -1:
		return dp[mask][t_shirt_id]
	ans = find(mask, t_shirt_id - 1)
	for e_id in t_shirts_elephant_map[t_shirt_id]:
		if mask & 1 << e_id > 0:
			ans += find(mask ^ 1 << e_id, t_shirt_id - 1)
	ans %= 1000000007
	dp[mask][t_shirt_id] = ans
	return ans
for t in range(int(input())):
	elephant_count = int(input())
	t_shirts_elephant_map = [list() for i in range(MAX_T_SHIRT)]
	dp = [[-1 for i in range(MAX_T_SHIRT)] for i in range(1 << elephant_count)]
	for elephant_id in range(elephant_count):
		t_shirts = [int(x) for x in input().split()]
		for t_shirt in t_shirts:
			t_shirts_elephant_map[t_shirt - 1].append(elephant_id)
	print(find((1 << elephant_count) - 1, MAX_T_SHIRT - 1))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = []
	mod = 10 ** 9 + 7
	ff = {}
	a = [[] for i in range(105)]
	for i in range(n):
		b = [int(x) for x in input().split()]
		for j in b:
			a[j].append(i)
			ff[j] = 1
	dp = [[0 for i in range(1025)] for j in range(105)]
	dp[0][0] = 1
	for i in range(1, 101):
		dp[i][0] = 1
		for j in range(len(a[i])):
			for mask in range(1024):
				if dp[i - 1][mask]:
					if mask & 1 << a[i][j] == 0:
						dp[i][mask | 1 << a[i][j]] += dp[i - 1][mask]
		for mask in range(1, 1024):
			if dp[i - 1][mask]:
				dp[i][mask] += dp[i - 1][mask]
	c = 0
	c = dp[100][(1 << n) - 1]
	c %= mod
	print(c)


dp = []
mod = 1000000007
p = 0

def solve(shirtNum, li, mask):
	if shirtNum == 101:
		if mask == p - 1:
			return 1
		else:
			return 0
	if dp[shirtNum][mask] != -1:
		return dp[shirtNum][mask]
	count = solve(shirtNum + 1, li, mask)
	for i in li[shirtNum]:
		if mask & 1 << i:
			continue
		count += solve(shirtNum + 1, li, mask | 1 << i)
	dp[shirtNum][mask] = count % mod
	return count % mod
for _ in range(int(input())):
	n = int(input())
	li = [[]] * 101
	dp = [[-1] * (1 << n) for i in range(102)]
	p = 1 << n
	for i in range(n):
		for ele in list(map(int, input().split())):
			if li[ele]:
				li[ele].append(i)
			else:
				li[ele] = [i]
	print(solve(1, li, 0))


t = int(input())
m = int(1000000000.0) + 7
allmask = 0

def solve(tss, dp, mask, tid):
	if mask == allmask:
		return 1
	if tid > 100:
		return 0
	if dp[mask][tid] != -1:
		return dp[mask][tid]
	ways = solve(tss, dp, mask, tid + 1)
	size = len(tss[tid])
	for j in range(size):
		if mask & 1 << tss[tid][j]:
			continue
		else:
			ways += solve(tss, dp, mask | 1 << tss[tid][j], tid + 1)
			ways %= m
	dp[mask][tid] = ways
	return ways
while t > 0:
	t -= 1
	n = int(input())
	tss = [[] for i in range(101)]
	for i in range(n):
		for tshirt in map(int, input().split()):
			tss[tshirt].append(i)
	dp = [[-1 for _ in range(101)] for _ in range((1 << n) + 1)]
	allmask = (1 << n) - 1
	print(solve(tss, dp, 0, 1))


import os, sys, math
from threading import Thread, stack_size
from collections import defaultdict as dd, deque
from bisect import bisect_left as bl, bisect as br
from heapq import heappush as push, heappop as pop, heapify
sys.setrecursionlimit(10 ** 6 + 999)
stack_size(2 ** 27)
BUFSIZE = 8192
mod = int(1000000000.0) + 7
mod2 = 998244353
yes = 'YES'
no = 'NO'
Yes = 'Yes'
No = 'No'
input = lambda : sys.stdin.readline().rstrip('\r\n')

def si():
	return input()

def msi():
	return input().split()

def mii():
	return [int(i) for i in input().split()]

def main():

	def solve(mask, tid):
		if mask == all_done:
			return 1
		if tid == 101:
			return 0
		if dp[mask, tid] != -1:
			return dp[mask, tid]
		else:
			ans = solve(mask, tid + 1)
			for i in d[tid]:
				if mask & 1 << i == 0:
					nmask = mask | 1 << i
					ans = ans % mod + solve(nmask, tid + 1) % mod
		dp[mask, tid] = ans % mod
		return ans % mod
	n = int(si())
	d = dd(list)
	all_done = (1 << n) - 1
	for i in range(n):
		for tshirts in msi():
			d[int(tshirts)].append(i)
	dp = dd(lambda : -1)
	ans = solve(0, 1) % mod
	print(ans)
TC = int(si())
for tc in range(TC):
	t = Thread(target=main)
	t.start()
	t.join()


def fun(tshirt, n, curTshirt, mask, dp):
	if mask == (1 << n) - 1:
		return 1
	if curTshirt > 100:
		return 0
	if (curTshirt, mask) in dp:
		return dp[curTshirt, mask]
	ans = fun(tshirt, n, curTshirt + 1, mask, dp)
	for i in tshirt[curTshirt]:
		if 1 << i & mask > 0:
			continue
		else:
			ans += fun(tshirt, n, curTshirt + 1, mask | 1 << i, dp)
	ans %= int(1000000000.0) + 7
	dp[curTshirt, mask] = ans
	return dp[curTshirt, mask]
for _ in range(int(input())):
	n = int(input())
	from collections import defaultdict
	tshirt = defaultdict(set)
	for i in range(n):
		lis = list(map(int, input().split()))
		for j in lis:
			tshirt[j].add(i)
	print(fun(tshirt, n, 1, 0, dict()))


try:
	mt = 100
	tsem = []
	ele = []

	def egt(m, tid):
		if m == 0:
			return 1
		if tid < 0:
			return 0
		if ele[m][tid] != -1:
			return ele[m][tid]
		result = egt(m, tid - 1)
		for eid in tsem[tid]:
			if m & 1 << eid > 0:
				result += egt(m ^ 1 << eid, tid - 1)
		result %= 1000000007
		ele[m][tid] = result
		return result
	for t in range(int(input())):
		ecnt = int(input())
		tsem = [list() for i in range(mt)]
		ele = [[-1 for i in range(mt)] for i in range(1 << ecnt)]
		for e_id in range(ecnt):
			tsh = [int(x) for x in input().split()]
			for ts in tsh:
				tsem[ts - 1].append(e_id)
		print(egt((1 << ecnt) - 1, mt - 1))
except EOFError as e:
	print(end='')


mod = 1000000007

def solve(mask, i):
	if dp[mask][i] != -1:
		return dp[mask][i]
	if mask == 2 ** n - 1:
		return 1
	if i == 101:
		return 0
	ways = solve(mask, i + 1)
	for p in c[i]:
		if mask & 1 << p:
			continue
		ways = (ways % mod + solve(mask | 1 << p, i + 1) % mod) % mod
	dp[mask][i] = ways
	return ways
t = int(input())
for x in range(t):
	n = int(input())
	dp = [[-1] * 102 for i in range(1026)]
	c = [[] for i in range(101)]
	for z in range(n):
		inp = list(map(int, input().split(' ')))
		for tshirt in inp:
			c[tshirt].append(z)
	print(solve(0, 0))


import collections
from functools import lru_cache
from collections import defaultdict
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 9)

def solve(n, arr):
	t2p = defaultdict(list)
	for (i, tshirtid) in enumerate(arr):
		for t in tshirtid:
			t2p[t].append(i)

	@lru_cache(None)
	def helper(k, mask):
		if mask == 2 ** n - 1:
			return 1
		if k == 101:
			return 0
		ans = helper(k + 1, mask)
		for p in t2p[k]:
			if mask & 1 << p:
				continue
			ans += helper(k + 1, mask | 1 << p)
		return ans % (10 ** 9 + 7)
	print(helper(1, 0))
t = int(input())
for _ in range(t):
	arr = []
	n = int(input())
	for _ in range(n):
		arr.append(list(map(int, input().split())))
	solve(n, arr)


I = input
t = int(I())
mod = int(1000000000.0 + 7)
end = 0
dp = []

def fun(mask, tid, ls):
	if mask == end:
		return 1
	if tid == 101:
		return 0
	if not dp[mask][tid] == -1:
		return dp[mask][tid]
	ans = 0
	ans += fun(mask, tid + 1, ls)
	for p in ls[tid]:
		if not mask >> p & 1:
			ans += fun(mask | 1 << p, tid + 1, ls)
	ans %= mod
	dp[mask][tid] = ans
	return ans
while t:
	n = int(I())
	end = (1 << n) - 1
	ls = []
	dp = []
	for i in range(1025):
		dp.append([-1] * 101)
	for i in range(101):
		ls.append([])
	for i in range(n):
		str = list(map(int, I().strip().split(' ')))
		for j in str:
			ls[j].append(i)
	print(fun(0, 1, ls))
	t -= 1


MOD = 1000000007
adj = [[] for x in range(101)]
dp = {}

def solve(tid, mask, n):
	if mask == (1 << n) - 1:
		return 1
	if tid >= 101:
		return 0
	if (tid, mask) in dp:
		return dp[tid, mask] % MOD
	c = 0
	c += solve(tid + 1, mask, n)
	for x in adj[tid]:
		if not 1 << x & mask:
			c = (c + solve(tid + 1, mask | 1 << x, n) % MOD) % MOD
	dp[tid, mask] = c % MOD
	return c % MOD
test = int(input())
for _ in range(test):
	n = int(input())
	mask = 0
	dp = {}
	adj = [[] for x in range(101)]
	for t in range(n):
		for x in input().split(' '):
			adj[int(x)].append(t)
	print(solve(1, mask, n) % MOD)


MOD = 1000000007
n = tshirt = dp = None
ass = set()

def allocate(mask, tid):
	if mask == (1 << n) - 1:
		return 1
	if tid == 101:
		return 0
	if dp[mask][tid] != -1:
		return dp[mask][tid]
	ans = allocate(mask, tid + 1)
	for p in tshirt[tid]:
		if mask >> p & 1:
			continue
		ans += allocate(mask | 1 << p, tid + 1)
	dp[mask][tid] = ans % MOD
	return ans % MOD
for _ in range(int(input())):
	tshirt = [[] for _ in range(101)]
	n = int(input())
	for p in range(n):
		for t in map(int, input().split()):
			tshirt[t].append(p)
	dp = [[-1] * 101 for _ in range(1 << n)]
	print(allocate(0, 1))


m = 10 ** 9 + 7

def bitmask(mask, tid):
	if mask == 2 ** n - 1:
		return 1
	if tid == 101:
		return 0
	if dp[mask][tid] != -1:
		return dp[mask][tid]
	ans = bitmask(mask, tid + 1)
	for h in ts[tid]:
		if mask & 1 << h:
			continue
		ans = (ans % m + bitmask(mask | 1 << h, tid + 1) % m) % m
	dp[mask][tid] = ans
	return ans
for _ in range(int(input())):
	n = int(input())
	dp = [[-1] * 102 for o in range(1024)]
	ts = [[] for i in range(101)]
	for j in range(n):
		l = list(map(int, input().split()))
		for k in l:
			ts[k].append(j)
	print(bitmask(0, 0))


def cek(mask, n):
	if mask == maxmask:
		return 1
	if n > 100:
		return 0
	if dp[mask][n] != -1:
		return dp[mask][n]
	ans = cek(mask, n + 1)
	for i in shirts[n]:
		if mask & 1 << i == 0:
			ans += cek(mask | 1 << i, n + 1)
	ans %= 10 ** 9 + 7
	dp[mask][n] = ans
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	shirts = [[] for x in range(101)]
	maxmask = (1 << n) - 1
	dp = [[-1 for x in range(101)] for y in range((1 << n) + 1)]
	for i in range(n):
		for j in sorted(map(int, input().split())):
			shirts[j].append(i)
	print(cek(0, 1))


from collections import defaultdict
mod = 10 ** 9 + 7

def solve(mask, i, n, new, res):
	if mask == 2 ** n - 1:
		return 1
	if i > 100:
		return 0
	if res[mask][i] >= 0:
		return res[mask][i]
	ans = solve(mask, i + 1, n, new, res)
	for j in new[i]:
		if mask & 1 << j == 0:
			ans += solve(mask | 1 << j, i + 1, n, new, res)
			ans %= mod
	res[mask][i] = ans
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	l = defaultdict(list)
	res = [[-1 for i in range(102)] for j in range(2 ** n + 1)]
	for i in range(n):
		t = [int(k) for k in input().split()]
		for j in t:
			l[i].append(j)
	new = defaultdict(list)
	for i in range(n):
		for j in l[i]:
			new[j].append(i)
	ans = solve(0, 1, n, new, res)
	print(ans % mod)


(M, Mod) = (105, 1000000007)
T = int(input())
for _ in range(0, T):
	n = int(input())
	b = [[] for i in range(M)]
	for i in range(0, n):
		a = list(map(int, input().split()))
		for j in range(0, len(a)):
			b[a[j]].append(i)
	dp = [[0] for i in range(M)]
	for i in range(0, M):
		dp[i] = [0] * (1 << n)
	dp[0][0] = 1
	for i in range(1, 101):
		for S in range(0, 1 << n):
			if dp[i - 1][S] == 0:
				continue
			dp[i][S] = (dp[i][S] + dp[i - 1][S]) % Mod
			for x in b[i]:
				if S & 1 << x:
					continue
				dp[i][S | 1 << x] = (dp[i][S | 1 << x] + dp[i - 1][S]) % Mod
	print(dp[100][(1 << n) - 1])


import sys
t = int(sys.stdin.readline().strip())
for tc in range(t):
	n = int(sys.stdin.readline().strip())
	A = []
	for i in range(n):
		A.append(set([int(c) for c in sys.stdin.readline().split()]))
	DP = []
	DP.append([1] + [0] * 100)
	for i in range(1, 2 ** n):
		DP.append([0] * 101)
	for t in range(1, 101):
		for mask in range(2 ** n):
			DP[mask][t] = DP[mask][t - 1]
		for mask in range(2 ** n):
			for p in range(n):
				if DP[mask][t - 1] == 0:
					continue
				if mask & 1 << p > 0:
					continue
				if t not in A[p]:
					continue
				DP[mask | 1 << p][t] += DP[mask][t - 1]
	print(DP[2 ** n - 1][100] % 1000000007)


mod = int(1000000000.0 + 7)
n = 0

def solve(mask, i, tshirt, dp):
	if mask == (1 << n) - 1:
		return 1
	if i > 100:
		return 0
	if dp[mask][i] != -1:
		return dp[mask][i]
	ways = solve(mask, i + 1, tshirt, dp)
	for j in tshirt[i]:
		j -= 1
		if mask & 1 << j:
			continue
		ways += solve(mask | 1 << j, i + 1, tshirt, dp)
		ways = ways % mod
	dp[mask][i] = ways
	return ways
for i in range(int(input())):
	tshirt = [[] for i in range(102)]
	dp = [[-1 for i in range(102)] for j in range((1 << 10) + 2)]
	n = int(input())
	for i in range(1, n + 1):
		l = list(map(int, input().split()))
		for j in l:
			tshirt[j].append(i)
	print(solve(0, 1, tshirt, dp))


from collections import defaultdict

class Dp_bit_masking_caps:

	def __init__(self):
		self.total_caps = 100
		self.cap_to_person_map = defaultdict(list)
		self.total_people = 0
		self.all_mask = 0

	def read_inputs_and_calculate_ways(self):
		self.total_people = int(input())
		self.all_mask = (1 << self.total_people) - 1
		for ppl in range(self.total_people):
			for cap in map(int, input().split()):
				self.cap_to_person_map[cap].append(ppl)
		self.cache = [[-1] * (self.total_caps + 1) for _ in range(2 ** self.total_people)]
		print(self.count_number_of_ways(0, 1))

	def count_number_of_ways(self, mask, cap_num):
		if mask == self.all_mask:
			return 1
		if cap_num > self.total_caps:
			return 0
		if self.cache[mask][cap_num] != -1:
			return self.cache[mask][cap_num]
		ways = self.count_number_of_ways(mask, cap_num + 1)
		for people_with_this_cap in self.cap_to_person_map[cap_num]:
			if mask & 1 << people_with_this_cap:
				continue
			ways += self.count_number_of_ways(mask | 1 << people_with_this_cap, cap_num + 1)
		ways = ways % (10 ** 9 + 7)
		self.cache[mask][cap_num] = ways
		return self.cache[mask][cap_num]

def main():
	number_of_test_cases = int(input())
	for i in range(number_of_test_cases):
		Dp_bit_masking_caps().read_inputs_and_calculate_ways()
main()


MOD = 1000000007
T = int(input())
SHIRTS = 101
for t in range(T):
	N = int(input())
	owns = [[False] * SHIRTS for _ in range(N)]
	for i in range(0, N):
		for s in map(int, input().split()):
			owns[i][s] = True
	dp = [[0] * (1 << N) for _ in range(SHIRTS)]
	dp[0][0] = 1
	for s in range(1, SHIRTS):
		for m in range(1 << N):
			dp[s][m] = dp[s - 1][m]
			for b in range(N):
				if m & 1 << b and owns[b][s]:
					dp[s][m] = (dp[s][m] + dp[s - 1][m ^ 1 << b]) % MOD
	print(dp[SHIRTS - 1][(1 << N) - 1])