Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given $M$ triplets $(X_{1}, Y_{1}, B_{1}), (X_{2}, Y_{2}, B_{2}), \ldots, (X_{M}, Y_{M}, B_{M})$. Find the number of sequences of positive integers $A_{1}, A_{2}, \ldots, A_{N}$ such that for each valid $i$, $\mathrm{lcm}(A_{X_{i}},A_{Y_{i}}) = B_{i}$, or determine that there is an infinite number of such sequences.

Since the answer can be very large, compute it modulo $1,000,000,007$ ($10^{9} + 7$). Note that the values $B_{1}, B_{2}, \ldots, B_{M}$ can also be very large ― you are given their prime decompositions.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$.
$M$ lines follow. For each $i$ ($1 ≤ i ≤ M$), the $i$-th of these lines contains three space-separated integers $X_{i}$, $Y_{i}$ and $R_{i}$, followed by a space and $2R_{i}$ space-separated integers $p_{1}, e_{1}, p_{2}, e_{2}, \ldots, p_{R_{i}}, e_{R_{i}}$, denoting that $B_{i} = \prod_{r=1}^{R_{i}} p_{r}^{e_{r}}$.

------  Output ------
For each test case, print a single line containing one integer ― the number of valid sequences modulo $1,000,000,007$, or $-1$ if there are infinitely many valid sequences.

------  Constraints ------
$1 ≤ T ≤ 3$
$0 ≤ M ≤ 10^{4}$
$1 ≤ N ≤ 38$
$1 ≤ X_{i}, Y_{i} ≤ N$ for each valid $i$
$0 ≤ R_{i} ≤ 200$ for each valid $i$
$p_{r}$ is a prime for each valid $r$
$p_{r} ≤ 10^{6}$ for each valid $r$
the total number of different primes $p_{r}$ in each test case does not exceed $5$
$1 ≤ e_{r} ≤ 10^{6}$ for each valid $r$

------  Subtasks ------
Subtask #1 (20 points, time limit 2 seconds): $N ≤ 20$

Subtask #2 (35 points, time limit 4 seconds): $N ≤ 30$

Subtask #3 (45 points, time limit 4.5 seconds): $T = 1$

----- Sample Input 1 ------ 
3

2 0

2 2

1 2 0

2 1 0

2 2

1 2 0

2 1 1 2 1
----- Sample Output 1 ------ 
-1

1

0
----- explanation 1 ------ 
Example case 1: Both elements of $A$ can be any positive integers, so there is an infinite number of valid sequences.

Example case 2: There are two constraints, but they are actually identical: $\mathrm{lcm}(A_{1}, A_{2}) = 1$. The only sequence that satisfies this is $A = [1, 1]$.

Example case 3: The two constraints contradict each other, so there is no valid sequence.

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Dynamic programming

Mathematics

Complete search


Solutions:
mod = 1000000007

def istrue(st, p, n, lis, lcm):
	if lcm[st][st][p] != -1 and lis[st] != lcm[st][st][p]:
		return 0
	for j in range(1, n + 1):
		if j == st or lcm[st][j][p] == -1:
			continue
		if max(lis[st], lis[j]) != lcm[st][j][p]:
			return 0
	return 1

def getans(st, pr, n, lis, lcm):
	if st > n:
		for i in range(1, n + 1):
			if istrue(i, pr, n, lis, lcm) == 0:
				return 0
		return 1
	(mmax, ans) = (-1, 0)
	if lcm[st][st][pr] != -1:
		lis[st] = lcm[st][st][pr]
	else:
		for j in range(1, n + 1):
			if j == st or lcm[st][j][pr] == -1:
				continue
			if lis[j] == -2:
				lis[st] = lcm[st][j][pr]
			if mmax == -1 or mmax > lcm[st][j][pr]:
				mmax = lcm[st][j][pr]
	if lis[st] != -1:
		ans = getans(st + 1, pr, n, lis, lcm)
	elif mmax == -1:
		ans = getans(st + 1, pr, n, lis, lcm)
		if ans != 0:
			return -1
		else:
			return 0
	elif mmax == 0:
		lis[st] = 0
		ans = getans(st + 1, pr, n, lis, lcm)
	else:
		(an1, an2) = (0, 0)
		lis[st] = -2
		an1 = getans(st + 1, pr, n, lis, lcm)
		lis[st] = mmax
		an2 = getans(st + 1, pr, n, lis, lcm)
		if an1 == -1 or an2 == -1:
			ans = -1
		else:
			ans = (an1 * mmax + an2) % mod
	lis[st] = -1
	return ans
t = int(input())
while t > 0:
	t = t - 1
	(n, m) = map(int, input().split())
	lcm = [[[-1 for i in range(5)] for j in range(n + 1)] for k in range(n + 1)]
	ok = 1
	dicta = {}
	for i in range(m):
		ele = list(map(int, input().split()))
		lis = [0] * 5
		(x, y, r) = (ele[0], ele[1], ele[2])
		for j in range(1, r + 1):
			(p, e) = (ele[2 + 2 * j - 1], ele[2 + 2 * j])
			if (p in dicta) == False:
				sz = len(dicta)
				dicta[p] = sz
			lis[dicta[p]] += e
		for j in range(0, 5):
			if lcm[x][y][j] == -1:
				(lcm[x][y][j], lcm[y][x][j]) = (lis[j], lis[j])
			if lcm[x][y][j] != lis[j]:
				ok = 0
	if ok == 0:
		print(0)
		continue
	ans = 1
	for pr in range(0, 5):
		lis = [-1] * (n + 1)
		pra = getans(1, pr, n, lis, lcm)
		if pra == 0:
			ans = 0
			break
		if pra == -1:
			ans = -1
		else:
			ans = pra * ans % mod
	print(ans)


def get_power_keys(A):
	keys = set()
	for row in A:
		for item in row:
			if item == -1:
				continue
			else:
				keys.update(item.keys())
	return keys

def give_count(n, constraints):
	if len(constraints) == 0:
		return -1
	A = [([-1] * n).copy() for _ in range(n)]
	for constraint in constraints:
		x = constraint[0] - 1
		y = constraint[1] - 1
		if x > y:
			(x, y) = (y, x)
		powers = get_power_dict(constraint[3:])
		if len(powers) > 5:
			raise Exception('Not possible')
		if A[x][y] != -1 and powers != A[x][y]:
			return 0
		else:
			A[x][y] = powers
	is_empty = [True] * n
	for x in range(n):
		for y in range(x, n):
			if A[x][y] != -1:
				is_empty[x] = False
				is_empty[y] = False
	for elem in is_empty:
		if elem:
			return -1
	max_possible = [A[x][x] for x in range(n)]
	for x in range(n):
		for y in range(x + 1, n):
			if A[x][y] == -1:
				continue
			if max_possible[x] == -1:
				max_possible[x] = A[x][y]
			else:
				max_possible[x] = get_max_possible_powers(A[x][y], max_possible[x])
			if max_possible[y] == -1:
				max_possible[y] = A[x][y]
			else:
				max_possible[y] = get_max_possible_powers(A[x][y], max_possible[y])
	min_possible = [{}.copy() for _ in range(n)]
	for x in range(n):
		if A[x][x] == -1:
			continue
		if is_possible(max_possible[x], A[x][x]):
			min_possible[x] = A[x][x]
		else:
			return 0
	for x in range(n):
		for y in range(x + 1, n):
			if A[x][y] == -1:
				continue
			x_possible = is_possible_with_powers(max_possible[x], A[x][y])
			y_possible = is_possible_with_powers(max_possible[y], A[x][y])
			min_possible_x = min_possible[x]
			min_possible_y = min_possible[y]
			for key in A[x][y]:
				if x_possible[key] == False and y_possible[key] == False:
					return 0
				elif x_possible[key] == False:
					if min_possible_y.get(key) is None:
						min_possible_y[key] = A[x][y][key]
					elif min_possible_y[key] != A[x][y][key]:
						return 0
				elif y_possible[key] == False:
					if min_possible_x.get(key) is None:
						min_possible_x[key] = A[x][y][key]
					elif min_possible_x[key] != A[x][y][key]:
						return 0
	power_keys = get_power_keys(A)
	return get_possibilities(min_possible, A, power_keys, max_possible)

def get_possibilities(min_power, A, power_keys, max_possible):
	n = len(A)
	power_possibilities = {}
	for power in power_keys:
		if power == 1:
			power_possibilities[1] = 1
			continue
		fixed_elems = [-1] * n
		for i in range(n):
			if min_power[i] != -1 and min_power[i].get(power) is not None:
				fixed_elems[i] = min_power[i][power]
		power_possibilities[power] = possibilities_helper(0, n, fixed_elems, A, power, max_possible)
	product = 1
	for value in power_possibilities.values():
		product *= value % 1000000007
	product %= 1000000007
	return product

def possibilities_helper(index, n, fixed_elem, A, power, max_possible):
	if index == n:
		return 1
	if fixed_elem[index] != -1 or max_possible[index].get(power) is None:
		return possibilities_helper(index + 1, n, fixed_elem, A, power, max_possible)
	for i in range(index):
		if A[i][index] != -1 and fixed_elem[i] == -1:
			return possibilities_helper(index + 1, n, fixed_elem, A, power, max_possible)
	fixed_elem[index] = max_possible[index][power]
	fixed = possibilities_helper(index + 1, n, fixed_elem, A, power, max_possible)
	fixed_elem[index] = -1
	return fixed + max_possible[index][power] * possibilities_helper(index + 1, n, fixed_elem, A, power, max_possible)

def is_possible(max_possible, lcm):
	for key in lcm:
		if key not in max_possible or max_possible[key] < lcm[key]:
			return False
	return True

def is_possible_with_powers(max_possible, lcm):
	to_return = {}
	for key in lcm:
		if key not in max_possible or max_possible[key] < lcm[key]:
			to_return[key] = False
		else:
			to_return[key] = True
	return to_return

def get_max_possible_powers(power1, power2):
	merged = {}
	for key1 in power1:
		if key1 in power2:
			merged[key1] = min(power1[key1], power2[key1])
	return merged

def get_power_dict(powers):
	if len(powers) == 0:
		return {1: 1}
	else:
		to_return = {}
		for i in range(len(powers) // 2):
			if to_return.get(powers[2 * i]) is not None:
				to_return[powers[2 * i]] += powers[2 * i + 1]
			else:
				to_return[powers[2 * i]] = powers[2 * i + 1]
		return to_return
T = input()
T = int(T)
for _ in range(T):
	(n, m) = [int(a) for a in input().split(' ')]
	constraints = []
	for _ in range(m):
		constraints.append([int(a) for a in input().split(' ')])
	print(give_count(n, constraints))


def calc(lcm_store, range_store, node, prime, mod, history):
	if node == 1:
		if range_store[node]['max'][prime] == range_store[node]['min'][prime]:
			history[node] = [range_store[node]['max'][prime]]
			ans = calc(lcm_store, range_store, node + 1, prime, mod, history.copy())
			return ans % mod
		else:
			ans = 0
			history[node] = [range_store[node]['min'][prime], range_store[node]['max'][prime] - 1]
			ans1 = calc(lcm_store, range_store, node + 1, prime, mod, history.copy())
			ans = (history[node][1] - history[node][0] + 1) * ans1 % mod
			history[node] = [range_store[node]['max'][prime]]
			ans2 = calc(lcm_store, range_store, node + 1, prime, mod, history.copy())
			ans = (ans + 1 * ans2) % mod
			return ans
	else:
		temp_node = []
		count_lcm = 0
		for n in range(1, node):
			if lcm_store[n][node] is not None:
				count_lcm = count_lcm + 1
				exp = lcm_store[n][node].get(p, 0)
				if exp > history[n][-1]:
					if range_store[node]['max'][p] < exp:
						return 0
					else:
						val = exp
						if len(temp_node) == 0:
							temp_node = [val]
						elif temp_node[0] <= val <= temp_node[-1]:
							temp_node = [val]
						else:
							return 0
				elif exp == history[n][-1]:
					val = [range_store[node]['min'][p], range_store[node]['max'][p]]
					if len(temp_node) == 1:
						if val[0] <= temp_node[0] <= val[1]:
							pass
						else:
							return 0
					elif len(temp_node) == 2:
						temp_node[0] = max(temp_node[0], val[0])
						temp_node[1] = min(temp_node[1], val[1])
						if temp_node[0] > temp_node[1]:
							temp_node = []
					else:
						temp_node = [val[0], val[1]]
		if count_lcm == 0:
			temp_node = [range_store[node]['min'][prime], range_store[node]['max'][prime]]
		if len(temp_node) == 0:
			return 0
		else:
			if node == len(range_store):
				if len(temp_node) == 1:
					return 1
				else:
					return (temp_node[1] - temp_node[0] + 1) % mod
			if len(temp_node) == 1:
				history[node] = temp_node
				return calc(lcm_store, range_store, node + 1, prime, mod, history.copy()) % mod
			elif temp_node[0] == temp_node[1]:
				history[node] = [temp_node[0]]
				return calc(lcm_store, range_store, node + 1, prime, mod, history.copy()) % mod
			else:
				ans = 0
				history[node] = [temp_node[0], temp_node[1] - 1]
				ans1 = calc(lcm_store, range_store, node + 1, prime, mod, history.copy()) % mod
				ans = (history[node][1] - history[node][0] + 1) * ans1 % mod
				history[node] = [temp_node[1]]
				ans2 = calc(lcm_store, range_store, node + 1, prime, mod, history.copy()) % mod
				ans = (ans + 1 * ans2) % mod
				return ans
for t in range(int(input())):
	(n, m) = list(map(int, input().split()))
	inconsistency = False
	lcm_store = [[None for j in range(n + 1)] for i in range(n + 1)]
	simple_store = []
	primes = set([])
	for i in range(m):
		l = list(map(int, input().split()))
		(a, b) = l[0:2]
		no = l[2]
		if a > b:
			(a, b) = (b, a)
		simple_store.append([a, b, no])
		if a > n or b > n:
			inconsistency = True
		if no != 0:
			stat = l[3:]
			if len(stat) < 2 * no:
				inconsistency = True
			temp_stat = {}
			for x in range(no):
				(base, exp) = (stat[2 * x], stat[2 * x + 1])
				temp_stat[base] = temp_stat.get(base, 0) + exp
			if lcm_store[a][b] is None:
				lcm_store[a][b] = {}
				for base in temp_stat:
					exp = temp_stat[base]
					lcm_store[a][b][base] = exp
					primes.add(base)
			else:
				for base in temp_stat:
					exp = temp_stat[base]
					if lcm_store[a][b].get(base, None) is None:
						inconsistency = True
					elif lcm_store[a][b].get(base, 0) != exp:
						inconsistency = True
					else:
						pass
		elif lcm_store[a][b] is None:
			lcm_store[a][b] = {}
		elif len(lcm_store[a][b]) > 0:
			inconsistency = True
	if m == 0:
		print('-1')
		continue
	if inconsistency:
		print('0')
		continue
	primes = list(primes)
	range_store = {i: {'min': {p: 0 for p in primes}, 'max': {p: 0 for p in primes}, 'minset': False, 'maxset': False} for i in range(1, n + 1)}
	inconsistency = False
	for (a, b, no) in simple_store:
		if a == b:
			if range_store[a]['maxset']:
				for p in primes:
					exp = lcm_store[a][b].get(p, 0)
					if exp != range_store[a]['max'][p]:
						inconsistency = True
						break
				if inconsistency:
					break
			if not range_store[a]['maxset']:
				for p in primes:
					exp = lcm_store[a][b].get(p, 0)
					range_store[a]['max'][p] = exp
					range_store[a]['min'][p] = exp
				range_store[a]['maxset'] = True
			continue
		if range_store[a]['maxset']:
			for p in primes:
				exp = lcm_store[a][b].get(p, 0)
				range_store[a]['max'][p] = min(range_store[a]['max'][p], exp)
		if not range_store[a]['maxset']:
			for p in primes:
				exp = lcm_store[a][b].get(p, None)
				if exp is None:
					range_store[a]['max'][p] = 0
				else:
					range_store[a]['max'][p] = exp
			range_store[a]['maxset'] = True
		if range_store[b]['maxset']:
			for p in primes:
				exp = lcm_store[a][b].get(p, 0)
				range_store[b]['max'][p] = min(range_store[b]['max'][p], exp)
		if not range_store[b]['maxset']:
			for p in primes:
				exp = lcm_store[a][b].get(p, None)
				if exp is None:
					range_store[b]['max'][p] = 0
				else:
					range_store[b]['max'][p] = exp
			range_store[b]['maxset'] = True
	if inconsistency:
		print('0')
		continue
	inconsistency = False
	for (a, b, no) in simple_store:
		for p in primes:
			exp = lcm_store[a][b].get(p, 0)
			(exp_a, exp_b) = (range_store[a]['max'][p], range_store[b]['max'][p])
			s_exp = max(exp_a, exp_b)
			if exp != s_exp:
				inconsistency = True
				break
			range_store[a]['min'][p] = max(range_store[a]['min'][p], 0 if exp == exp_b else exp)
			range_store[b]['min'][p] = max(range_store[b]['min'][p], 0 if exp == exp_a else exp)
			if range_store[a]['min'][p] > range_store[a]['max'][p] or range_store[b]['min'][p] > range_store[b]['max'][p]:
				inconsistency = True
				break
		if inconsistency:
			break
	if inconsistency:
		print('0')
		continue
	mod = 10 ** 9 + 7
	infinite = False
	valid_seq = 1
	for el in range_store:
		if not range_store[el]['maxset']:
			infinite = True
			break
	if infinite:
		print('-1')
		continue
	for p in primes:
		valid_seq = valid_seq * calc(lcm_store, range_store, 1, p, mod, [None for i in range(n + 1)]) % mod
	print(valid_seq)


def getDisjoint(i, v):
	disjoint = set()
	q = {i}
	while len(q) > 0:
		pnt = q.pop()
		disjoint.add(pnt)
		for (ppnt, _) in link[pnt]:
			if ppnt not in disjoint:
				q.add(ppnt)
	return disjoint

def validate(i):
	for (pnt, dic) in link[i]:
		if v in tlink[pnt] and v in tlink[i]:
			if max(tlink[pnt].get(v, 0), tlink[i].get(v, 0)) != dic.get(v, 0):
				return False
	return True

def recur(i, v):
	visited[i] = True
	ans = 0
	max_num = float('inf')
	for (pnt, dic) in link[i]:
		if v not in dic:
			max_num = 0
			break
		else:
			max_num = min(max_num, dic[v])
	if len(disjoint) == 0:
		tlink[i][v] = 0
		ans += max_num * validate(i)
		del tlink[i][v]
		tlink[i][v] = max_num
		ans += validate(i)
		del tlink[i][v]
		return ans
	else:
		pnt = disjoint.pop()
		tlink[i][v] = 0
		if validate(i):
			ans += max_num * recur(pnt, v)
		del tlink[i][v]
		tlink[i][v] = max_num
		if validate(i):
			ans += recur(pnt, v)
		del tlink[i][v]
		disjoint.add(pnt)
		return ans % mod
mod = 1000000007
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	link = [[] for _ in range(n)]
	primes = set()
	for _ in range(m):
		(x, y, r, *pe) = map(int, input().split())
		dic = {}
		for i in range(0, 2 * r, 2):
			(p, e) = (pe[i], pe[i + 1])
			dic[p] = dic.get(p, 0) + e
			primes.add(p)
		x -= 1
		y -= 1
		link[x].append([y, dic])
		link[y].append([x, dic])
	ans = 1
	for l in link:
		if len(l) == 0:
			ans = -1
			break
	if ans != -1:
		for v in primes:
			tlink = [{} for _ in range(n)]
			visited = [False for _ in range(n)]
			for i in range(n):
				if not visited[i]:
					disjoint = getDisjoint(i, v)
					disjoint.remove(i)
					ans = ans * recur(i, v) % mod
			if ans == 0:
				break
	print(ans)


t = int(input())
for hatt in range(t):
	lis = input().split()
	(n, m) = (int(lis[0]), int(lis[1]))
	pairs = []
	lcmfac = []
	primelis = []
	for hatt in range(m):
		lis = input().split()
		(x, y) = (int(lis[0]) - 1, int(lis[1]) - 1)
		pairs.append((x, y))
		r = int(lis[2])
		faclis = {}
		for i in range(r):
			(p, e) = (int(lis[2 * i + 3]), int(lis[2 * i + 4]))
			if p not in primelis:
				primelis.append(p)
			if p not in faclis:
				faclis[p] = e
			else:
				faclis[p] += e
		lcmfac.append(faclis)
	ans = 1
	infiniteflag = False
	zeroflag = False
	if len(primelis) > 0:
		for hatu in primelis:
			fixed = [False] * n
			a = [-1] * n
			for i in range(m):
				(x, y) = pairs[i]
				if hatu not in lcmfac[i]:
					coun = 0
				else:
					coun = lcmfac[i][hatu]
				if x == y:
					if not fixed[x]:
						fixed[x] = True
						if a[x] != -1 and a[x] < coun:
							zeroflag = True
						a[x] = coun
					elif a[x] != coun:
						zeroflag = True
				else:
					if a[x] == -1:
						a[x] = coun
					if a[y] == -1:
						a[y] = coun
					if not fixed[x]:
						a[x] = min(a[x], coun)
					elif a[x] > coun:
						zeroflag = True
					if not fixed[y]:
						a[y] = min(a[y], coun)
					elif a[y] > coun:
						zeroflag = True
			if not zeroflag:
				for i in range(m):
					(x, y) = pairs[i]
					if hatu not in lcmfac[i]:
						coun = 0
					else:
						coun = lcmfac[i][hatu]
					if x != y:
						if a[x] < coun:
							if a[y] < coun:
								zeroflag = True
							else:
								fixed[y] = True
						elif a[y] < coun:
							fixed[x] = True
				if not zeroflag:
					dependlis = [[] for i in range(n)]
					for i in range(m):
						(x, y) = pairs[i]
						if x != y:
							if not fixed[x] and (not fixed[y]):
								(x, y) = (min(x, y), max(x, y))
								if y not in dependlis[x]:
									dependlis[x].append(y)
					for i in range(n):
						if a[i] == -1:
							infiniteflag = True
					if not infiniteflag:
						primemod = 1000000007

						def finds(currind, banlist):
							if fixed[currind]:
								if currind == n - 1:
									return 1
								else:
									return finds(currind + 1, banlist)
							elif currind == n - 1:
								if currind in banlist:
									return 1
								else:
									return (1 + a[currind]) % primemod
							elif currind in banlist:
								return finds(currind + 1, banlist)
							elif dependlis[currind] and a[currind] > 0:
								banlist2 = banlist.copy()
								for i in dependlis[currind]:
									if i not in banlist2:
										banlist2.append(i)
								return (finds(currind + 1, banlist) + a[currind] * finds(currind + 1, banlist2) % primemod) % primemod
							else:
								return (1 + a[currind]) * finds(currind + 1, banlist) % primemod
						aaa = 0
						aaa = finds(0, [])
						ans = ans * aaa % primemod
	else:
		occur = [0] * n
		for (x, y) in pairs:
			occur[x] += 1
			occur[y] += 1
		for i in range(n):
			if occur[i] == 0:
				infiniteflag = True
	if zeroflag:
		print(0)
	elif infiniteflag or m == 0:
		print(-1)
	else:
		print(ans)