Chef has arrived in Dagobah to meet with Yoda to study cooking. Yoda is a very busy cook and he doesn't want to spend time with losers. So he challenges the Chef to a series of games, and agrees to teach the Chef if Chef can win at least P of the games. The total number of games is K. The games will be played on a chessboard of size N*M. That is, it has N rows, each of which has M squares. At the beginning of the game, a coin is on square (1, 1), which corresponds to the top-left corner, and every other square is empty. At every step, Yoda and Chef have to move the coin on the chessboard. The player who cannot make a move loses. Chef makes the first move. They can't move the coin to a square where it had been placed sometime before in the game, and they can't move outside chessboard.

In this game, there are two different sets of rules according to which the game can be played:

-from (x, y) player can move coin to (x+1, y), (x-1, y), (x, y+1), (x, y-1) in his turn, if they are valid squares.

-from (x, y) player can move coin to (x+1, y+1), (x-1, y-1), (x-1, y+1), (x+1, y-1) in his turn, if they are valid squares.

Before every game, the Power of the kitchen chooses one among the two sets of rules with equal probability of 0.5, and the game will be played according to those rules. Chef and Yoda are very wise, therefore they play optimally. You have to calculate the probability that Yoda will teach Chef.

-----Input-----

Input begins with an integer T, the number of test cases

Each test case begins with 4 integers N, M, P, K.

-----Output-----

For each test case, output a line containing the answer for task. The output must have an absolute error at most 0.000001 (10-6).  

-----Constraints and Subtasks-----
-  1 ≤ T ≤ 50 
-  1 ≤ K 

Subtask 1 : 10 points 

-  2 ≤ N, M ≤ 5 
-  0 ≤ P ≤ K ≤ 5 

Subtusk 2 : 10 points 
-  2 ≤ N, M ≤ 10 
-  0 ≤ P ≤ K ≤ 10^3 

Subtusk 3 : 20 points 
-  2 ≤ N, M ≤ 100 
-  0 ≤ P ≤ K ≤ 10^3 

Subtusk 4 : 60 points
-  2 ≤ N, M ≤ 100 
-  0 ≤ P ≤ K ≤ 10^6 

-----Example-----
Input:
2
2 3 2 3
2 2 5 5
Output:
0.500000
1.000000

Difficulty: HARD

Starter code:

Solutions:
import math
dp = []
dp.append(0)
for i in range(1, 1000005):
	dp.append(math.log(i) + dp[i - 1])
t = int(input())
for i in range(t):
	(n, m, p, k) = input().split()
	n = int(n)
	m = int(m)
	p = int(p)
	k = int(k)
	if p == 0 or (n % 2 == 0 and m % 2 == 0):
		ans = 1.0
		print(ans)
	elif n % 2 == 1 and m % 2 == 1:
		ans = 0.0
		print(ans)
	else:
		P = 0
		kln2 = k * math.log(2)
		for i in range(p, k + 1):
			lnPi = dp[k] - dp[i] - dp[k - i] - kln2
			Pi = pow(math.e, lnPi)
			P += Pi
		print(P)


import math
lnfact = [0, 0]
for i in range(2, int(1000000.0) + 1):
	lnfact.append(lnfact[-1] + math.log(i))

def calc(p, k):
	P = 0
	kln2 = k * math.log(2)
	for i in range(p, k + 1):
		lnPi = lnfact[k] - lnfact[i] - lnfact[k - i] - kln2
		Pi = pow(math.e, lnPi)
		P += Pi
	return P
for t in range(int(input())):
	(n, m, p, k) = map(int, input().split())
	if p == 0 or (n % 2 == 0 and m % 2 == 0):
		print(1.0)
	elif n % 2 == 1 and m % 2 == 1:
		print(0.0)
	else:
		print(calc(p, k))


import sys
MAX = 1000005
INF = 1e+40

def solve(p, k):
	curr = 1
	ctr = min(100, k)
	i = 1
	while i <= ctr:
		curr /= 2.0
		i += 1
	ans = curr
	if p >= k / 2:
		i = k - 1
		while i >= p:
			curr *= i + 1
			curr /= k - i
			ans += curr
			if curr >= INF:
				while ctr < k and curr >= INF:
					ctr += 1
					curr /= 2.0
					ans /= 2.0
			i -= 1
		i = ctr + 1
		while i <= k:
			ans /= 2.0
			i += 1
	else:
		i = 1
		while i < p:
			curr *= k - i + 1
			curr /= i
			ans += curr
			if curr >= INF:
				while ctr < k and curr >= INF:
					ctr += 1
					curr /= 2.0
					ans /= 2.0
			i += 1
		i = ctr + 1
		while i <= k:
			ans /= 2.0
			i += 1
		ans = 1.0 - ans
	return ans
inpos = sys.stdin
t = int(inpos.readline())
for _ in range(t):
	inp = list(map(int, inpos.readline().split()))
	n = inp[0]
	m = inp[1]
	p = inp[2]
	k = inp[3]
	if p == 0:
		ans = 1.0
	elif n % 2 == 0 and m % 2 == 0:
		ans = 1.0
	elif n % 2 == 0 or m % 2 == 0:
		ans = solve(p, k)
	else:
		ans = 0.0
	print('{0:.10f}'.format(ans))


from math import erf, sqrt

def foo(n, r):
	r += 1
	(ans, x) = (1, 1)
	(p, q) = (n, 1)
	for i in range(1, r):
		x = p * x / q
		p -= 1
		q += 1
		ans += x
	return ans

def phi(x):
	return (1.0 + erf(x / sqrt(2.0))) / 2.0
T = int(input())
for t in range(T):
	(N, M, P, K) = map(int, input().strip().split())
	ans = 1
	if P != 0:
		(yoda1, yoda2) = (M & 1 and N & 1, M & 1 or N & 1)
		if yoda1 & yoda2:
			ans = 0
		elif yoda1 or yoda2:
			if K <= 1020:
				d = pow(2, K)
				if P <= K - P:
					n = d - foo(K, P - 1)
				else:
					n = foo(K, K - P)
				ans = n / d
			else:
				ans = phi((K - P + 0.5 - 0.5 * K) / sqrt(K * 0.25))
	ans = round(ans, 6)
	print(ans)


import math
t = int(input())
logfact = []
logfact.append(0)
for i in range(1, 1000001):
	logfact.append(logfact[i - 1] + math.log2(i))
while t > 0:
	(n, m, p, k) = map(int, input().split())
	winner1 = True
	winner2 = False
	ans = 0.0
	if n & 1 == 1 and m & 1 == 1:
		winner1 = False
	if n & 1 == 0 and m & 1 == 0:
		winner2 = True
	if winner1 == False and winner2 == False:
		if p == 0:
			ans = 1.0
		else:
			ans = 0.0
	elif winner1 == True and winner2 == True:
		ans = 1.0
	else:
		t1 = 1.0
		val = 1.0
		for i in range(1, k - p + 1):
			div = 1.0 * k - t1 + 1.0
			val = val * t1 / div + 1.0
			t1 += 1.0
		pw = math.log2(val) + logfact[k] - k - logfact[p] - logfact[k - p]
		ans = 2 ** pw
	print(float('{0:.9f}'.format(ans)))
	t -= 1


import sys
MAX = 1000005
INF = 1e+40

def binomial_sum(N, K):
	(current_exponent, current_mantissa) = (0, 1.0)
	(total_exponent, total_mantissa) = (0, 1.0)
	for i in range(1, K + 1):
		current_mantissa = (N - i + 1) * current_mantissa / i
		while current_mantissa >= 2:
			current_mantissa /= 2
			current_exponent += 1
		while current_mantissa <= 0.5:
			current_mantissa *= 2
			current_exponent -= 1
		total_mantissa += current_mantissa * pow(2, current_exponent - total_exponent)
		while total_mantissa >= 2:
			total_mantissa /= 2
			total_exponent += 1
	return (total_exponent, total_mantissa)

def solve(p, k):
	curr = 1
	ctr = min(100, k)
	i = 1
	while i <= ctr:
		curr /= 2.0
		i += 1
	ans = curr
	if p >= k / 2:
		i = k - 1
		while i >= p:
			curr *= i + 1
			curr /= k - i
			ans += curr
			if curr >= INF:
				while ctr < k and curr >= INF:
					ctr += 1
					curr /= 2.0
					ans /= 2.0
			i -= 1
		i = ctr + 1
		while i <= k:
			ans /= 2.0
			i += 1
	else:
		i = 1
		while i < p:
			curr *= k - i + 1
			curr /= i
			ans += curr
			if curr >= INF:
				while ctr < k and curr >= INF:
					ctr += 1
					curr /= 2.0
					ans /= 2.0
			i += 1
		i = ctr + 1
		while i <= k:
			ans /= 2.0
			i += 1
		ans = 1.0 - ans
	return ans
inpos = sys.stdin
t = int(inpos.readline())
for _ in range(t):
	inp = list(map(int, inpos.readline().split()))
	n = inp[0]
	m = inp[1]
	p = inp[2]
	k = inp[3]
	if p == 0:
		ans = 1.0
	elif n % 2 == 0 and m % 2 == 0:
		ans = 1.0
	elif n % 2 == 0 or m % 2 == 0:
		if k <= MAX:
			ans = solve(p, k)
		elif p <= MAX or k - p <= MAX:
			ans = solve(p, k)
		else:
			g1 = binomial_sum(k, p - 1)
			u = g1[0] - k
			ans = g1[1]
			while u < 0:
				ans /= 2.0
				u += 1
			ans = 1.0 - ans
	else:
		ans = 0.0
	print('{0:.10f}'.format(ans))


import math
dp = []
dp.append(0)
for i in range(1, 1000005):
	dp.append(math.log(i) + dp[i - 1])
t = int(input())
for i in range(t):
	(n, m, p, k) = input().split()
	n = int(n)
	m = int(m)
	p = int(p)
	k = int(k)
	if n % 2 == 0 and m % 2 == 0:
		ans = 1.0
		print(ans)
	elif n % 2 == 1 and m % 2 == 1:
		ans = 0.0
		print(ans)
	else:
		ans = 0
		for j in range(p, k + 1):
			total = math.exp(dp[k] - dp[j] - dp[k - j] - k * math.log(2))
			ans = ans + total
		print(ans)


import math
la = [0, 0]
for i in range(2, int(1000000.0) + 1):
	la.append(la[-1] + math.log(i))

def calc(p, k):
	s = 0
	kl2 = k * math.log(2)
	for i in range(0, p + 1):
		lgpi = la[k] - la[i] - la[k - i] - kl2
		pi = pow(math.e, lgpi)
		s += pi
	return s
for t in range(int(input())):
	(n, m, p, k) = map(int, input().split())
	if p == 0 or (n % 2 == 0 and m % 2 == 0):
		print(1.0)
	elif n % 2 == 1 and m % 2 == 1:
		print(0.0)
	else:
		p = k - p
		print(calc(p, k))