Read problems statements in Mandarin Chinese  and Russian. 
Sereja is playing a game called Winner Eats Sandwich with his friends. There are N persons in total, including Sereja. Sereja is allotted the number 1, while his friends are allotted numbers from 2 to N. A set of this game consists of M parts. Probability that a player numbered i wins part j of any set is p[i][j]. Sereja and his friends play all the M parts of the first set. If someone wins all the parts, he is declared the winner of the match. Otherwise, another set of the game is played. A match of the game continues until someone wins a set. The winner of the set is then declared the winner of the game, and gets to eat the sandwich.
Now Sereja is interested in the probability with which he can win the match in no more than 10^(10^(10^(10^(10^{10})))) sets. This is because the sandwich gets cold by the end of these many sets, and Sereja hates cold sandwiches.

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

First line contains the number of test cases, T. The description of the T tests follows. First line of each test case contains two space separated integers N, M. Each of the next N lines contain M space-separated numbers, with the j^{th} number of the i^{th} line denoting p[i][j]. All numbers will be given with not more than 4 digits after the decimal point.

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

For each test case, output the probability Sereja is interested in, with 6 digits after the decimal point.

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

$1 ≤ T ≤ 3$
$1 ≤ N ≤ 13$
$1 ≤ M ≤ 10000$
$it is guaranteed that for each j, the sum p[1][j] + p[2][j] + ... + p[N][j] is 1$

Subtask 1 (10 points)

$1 ≤ N, M ≤ 4$

Subtask 2 (90 points)

$Original constrains$

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

Input:
2
2 2
1.0000 1.0000
0.0000 0.0000
2 3
0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 

Output:
1.000000
0.500000

Difficulty: VERY_HARD
Tags: Mathematics

Probability

Starter code:

Solutions:
from fractions import *

def main():
	T = int(input())
	for t in range(T):
		(N, M) = [int(x) for x in input().split()]
		A = []
		for i in range(N):
			row = input().split()
			for j in range(len(row)):
				if '.' not in row[j]:
					while True:
						y = 1
				row[j] = int(10000 * (eval(row[j]) + 2e-05))
			A.append(row)
		Pw = 1
		for j in range(M):
			Pw *= A[0][j]
			if Pw == 0:
				break
		if Pw == 0:
			print('0.000000')
			continue
		wins = Pw
		for i in range(1, N):
			tmp = 1
			for j in range(M):
				tmp *= A[i][j]
				if tmp == 0:
					break
			wins += tmp
		print('%0.6f' % Fraction(Pw / wins))
main()


import math
import decimal

def main():
	t = int(input())
	i = 0
	while i < t:
		iarr = input().split()
		n = int(iarr[0])
		m = int(iarr[1])
		j = 0
		sum = 0
		prod1 = 1
		k = 0
		arr = input().split()
		while k < m:
			temp2 = math.floor(decimal.Decimal(arr[k]) * 10000 + decimal.Decimal(0.5))
			prod1 = prod1 * temp2
			k = k + 1
		sum = sum + prod1
		j = 0
		while j < n - 1:
			prod = 1
			k = 0
			arr = input().split()
			while k < m:
				temp2 = math.floor(decimal.Decimal(arr[k]) * 10000 + decimal.Decimal(0.5))
				prod = prod * temp2
				k = k + 1
			sum = sum + prod
			j = j + 1
		if prod1 == 0:
			print(0.0)
		else:
			print(format(decimal.Decimal(prod1) / sum, '.6f'))
		i = i + 1
main()


from decimal import *
import math
t = int(input())
for i in range(0, t):
	(n, m) = map(int, input().split())
	prob = Decimal(1)
	for j in input().split():
		prob = prob * Decimal(j)
	sumprob = prob
	for j in range(1, n):
		tprobi = Decimal(1)
		for k in input().split():
			tprobi = tprobi * Decimal(k)
		sumprob = sumprob + tprobi
	if prob > 0.0:
		print('{0:.6f}'.format(prob / sumprob))
	else:
		print('{0:.6f}'.format(Decimal(0)))


import math
from decimal import *
t = int(input())
b = [0.0] * 1000000
c = [0.0] * 1000000
d = [0.0] * 1000000
k = 0
go = float(0.0)
while t:
	t = t - 1
	(n, m) = map(int, input().split())
	sum1 = 0.0
	for i in range(1, n + 1):
		g = m
		b = list(map(float, input().split()))
		for k in range(1, m + 1):
			c[k] = b[k - 1]
		while g != 1:
			if g % 2 == 0:
				v = int(g / 2)
				j = 1
				for k in range(1, v + 1):
					d[k] = Decimal(c[j]) * Decimal(c[j + 1])
					j = j + 2
				for k in range(1, v + 1):
					c[k] = Decimal(d[k])
				g = v
			else:
				v = int(g / 2)
				j = 1
				for k in range(1, v + 1):
					d[k] = Decimal(c[j]) * Decimal(c[j + 1])
					j = j + 2
				d[v + 1] = c[g]
				for k in range(1, v + 2):
					c[k] = Decimal(d[k])
				g = v + 1
		if i == 1:
			go = Decimal(c[1])
		sum1 = Decimal(sum1) + Decimal(c[1])
	if sum1 == 0:
		go = 0.0
	else:
		go = Decimal(Decimal(go) / Decimal(sum1))
	print(format(go, '.6f'))


t = int(input())
for z in range(t):
	(n, k) = map(int, input().split())
	tot = 0
	first = 0
	for i in range(n):
		a = list(map(float, input().split()))
		cur = 1
		for j in range(k):
			cur = cur * round(a[j] * 10000)
		tot += cur
		if i == 0:
			first = cur
	if tot == 0:
		print('%.9f' % 0)
	else:
		print('%.9f' % (first / tot))


from decimal import Decimal

def solve(N, M):
	a = Decimal(1.0)
	c = Decimal(0.0)
	prob = []
	for i in range(N):
		prob = input().split()
		prob = [Decimal(p) for p in prob]
		b = Decimal(1.0)
		for j in range(M):
			b = b * prob[j]
		if i == 0:
			a = b
		c += b
	if c == 0:
		return 0
	else:
		ans = Decimal(a / c)
		return ans

def main():
	T = int(input())
	for t in range(T):
		(N, M) = map(int, input().split())
		e = solve(N, M)
		print('%.12f' % e)
	return 0
main()


import functools
from decimal import Decimal
from operator import mul
t = int(input())
for jj in range(t):
	(n, m) = map(int, input().split())
	a = [0] * n
	num = 1
	for i in range(n):
		a[i] = list(map(Decimal, input().split()))
		if i == 0:
			num = Decimal(functools.reduce(mul, a[i]))
	temp = 0
	if num == 0:
		print(0)
		continue
	for j in range(n):
		den = 1
		den = Decimal(functools.reduce(mul, a[j]))
		den = den / num
		temp += den
	x = 1 / temp
	print(x)


t = int(input())
while t:
	t -= 1
	s = input()
	st = s.split()
	n = int(st[0])
	m = int(st[1])
	summ = 0
	for i in range(n):
		prod = 1
		s = input()
		f = s.split()
		for j in range(m):
			leng = len(f[j])
			if leng == 6:
				gg = int(f[j][5]) + 10 * int(f[j][4]) + 100 * int(f[j][3]) + 1000 * int(f[j][2]) + 100000 * int(f[j][0])
			elif leng == 5:
				gg = 10 * int(f[j][4]) + 100 * int(f[j][3]) + 1000 * int(f[j][2]) + 100000 * int(f[j][0])
			elif leng == 4:
				gg = 100 * int(f[j][3]) + 1000 * int(f[j][2]) + 100000 * int(f[j][0])
			elif leng == 3:
				gg = 1000 * int(f[j][2]) + 100000 * int(f[j][0])
			elif leng == 1:
				gg = 100000 * int(f[j][0])
			prod *= gg
		if i == 0:
			saved = prod
		summ += prod
	if summ == 0:
		print('0.000000')
	else:
		xr = saved / summ
		print('%.6f' % xr)


inp = int(input())
while inp:
	inp -= 1
	li = list(map(int, input().split()))
	n = li[0]
	m = li[1]
	total = 0
	for i in range(n):
		term = int(1)
		strt = input()
		li = strt.split()
		for j in range(m):
			length = len(li[j])
			tt = int(100000) * int(li[j][0])
			param = int(10000)
			for k in range(3, length + 1):
				tt = tt + int(param) * int(li[j][k - 1])
				param //= 10
			term = term * tt
		if i == 0:
			sereja = term
		total = total + term
	if total == 0:
		print('0.000000')
	else:
		div = sereja / total
		print('%.6f' % div)


t = int(input())
for it in range(t):
	(n, m) = [int(word) for word in input().split()]
	wsig = [1.0] * 13
	wpower = [0] * 13
	is_zero = [False] * 13
	all_zero = True
	for i in range(n):
		words = input().split()
		for j in range(m):
			ival = int(words[j][0] + words[j][2:])
			if ival == 0:
				is_zero[i] = True
				wsig[i] = 0
				break
			fval = float(words[j])
			wsig[i] *= fval
			while wsig[i] < 1.0:
				wpower[i] -= 4
				wsig[i] *= 10000.0
		if not is_zero[i]:
			all_zero = False
	if all_zero:
		res = 0
	else:
		maxpower = max(wpower)
		wsum = 0.0
		for i in range(n):
			wpower[i] -= maxpower
			wsum += wsig[i] * 10 ** wpower[i]
		w0 = wsig[0] * 10 ** wpower[0]
		res = w0 / wsum
	print('%.6f' % res)


from decimal import *
getcontext().prec = 100

def main():
	t = int(input())
	for test in range(t):
		p = []
		(n, m) = list(map(int, input().split(' ')))
		for i in range(n):
			x = input().strip().split(' ')
			inp = list(map(Decimal, x))
			p.append(inp)
		a = Decimal('1.0')
		for i in range(m):
			a *= p[0][i]
		s = Decimal('0.0')
		for i in range(1, n):
			b = Decimal('1.0')
			for j in range(m):
				b *= p[i][j]
			s += b
		if a + s == 0:
			ans = 0
		else:
			ans = a / (a + s)
		print('{0:.6f}'.format(ans))
	return 0
main()


def getin():
	while True:
		line = input().strip()
		if not line:
			pass
		else:
			return line
t = int(getin())
for i in range(t):
	(n, m) = map(int, getin().split())
	if n < 1 or m < 1:
		pa = throwerror
	ts = 0
	for j in range(n):
		ls = [25 * float(temp) for temp in getin().split()]
		s = 1
		for k in range(m):
			s = s * ls[k]
		if j == 0:
			sj = s
		ts = ts + s
	if ts == 0:
		ans = 0.0
	else:
		ans = float(sj / ts)
	print('{:.10f}'.format(ans))


import math
TT = int(input())
while TT > 0:
	TT -= 1
	(n, m) = map(int, input().split())
	res1 = 1
	res2 = 0
	a = list(map(float, input().split()))
	for i in range(0, m):
		res1 *= int(round(10000 * a[i]))
	res2 = res1
	for i in range(1, n):
		a = list(map(float, input().split()))
		t = 1
		for j in range(0, m):
			t *= int(round(10000 * a[j]))
		res2 += t
	if res2 != 0:
		print('%.6f' % (res1 / res2))
	else:
		print(0.0)


import sys
import functools
T = int(sys.stdin.readline())
for _ in range(T):
	(n, m) = map(int, sys.stdin.readline().split())
	p = []
	for i in range(n):
		t = 1
		for s in sys.stdin.readline().split():
			t *= int((float(s) + 1e-06) * 10000)
		p.append(t)
	if p[0] == 0:
		print('0.000000')
	else:
		t = p[0]
		q = [float(x / t) for x in p]
		print('%.06lf' % (1 / sum(q)))


def solve():
	(n, m) = (int(s) for s in input().split())
	ser = 0
	total = 0
	for i in range(n):
		inp = input().split()
		th = 1
		for j in range(m):
			th *= int(round(float(inp[j]) * 10000))
		if i == 0:
			ser = th
		total += th
	if total == 0:
		print('0.000000')
	else:
		print('%.6f' % (ser / total))
testcase = int(input())
for i in range(testcase):
	solve()


import math
from decimal import *
t = int(input())
while t:
	t = t - 1
	(n, m) = map(int, input().split())
	for i in range(1, n + 1):
		b = list(map(float, input().split()))
		s = 1.0
		for j in range(0, m):
			s = Decimal(s) * Decimal(b[j])
		if i == 1:
			sum1 = Decimal(s)
			go = Decimal(s)
		else:
			sum1 = Decimal(sum1) + Decimal(s)
	if sum1 != 0:
		go = Decimal(go) / Decimal(sum1)
	else:
		go = 0.0
	print(format(go, '.6f'))