Bear Limak is a dance teacher.
Today is the first day of the course.
The course will take one or more days.
Your task will be to calculate the expected value of the number of dances in the course.

There are $n$ boys and $m$ girls.
A classroom is very small and thus only one pair can dance at each moment.
For each new dance Limak chooses uniformly at random one boy and one girl.
The chosen pair will dance, unless the following will happen.

It's possible that the chosen pair has already danced with each other on the same day.
Then, with probability ${r}$ they will now get upset about it and they will refuse to dance (but otherwise they dance like a normal pair).
In such a situation Limak will apologize them and there will be no more dances on that day.
Classes will start again on the next day though, and Limak won't care who danced the day before and who got angry.
So, the situation will be exactly as on the first day.

Limaks waits for the possibility to say "Nice, kids. Every person has danced today. The course is over!".
So, the course ends immediately when there is a situation that every person has danced on that day.
What is the expected value of the number of dances in the course?

Input Format

The only line of the input contains two integers $n$, $m$, and one real number ${r}$.

Constraints  

$1\leq n\leq30$  
$1\leq m\leq30$  
$0.001\leq r\leq0.1$  
${r}$ is given with at most ${6}$ places after the decimal point.

Output Format

Find and print the expected value of the number of dances in the course.
The answer will be considered correct if the absolute or relative error doesn't exceed ${10^{-6}}$.

Sample Input 0

1 2 0.062812

Sample Output 0

3.0000000000

Sample Input 1

2 3 0.075

Sample Output 1

5.8901549035

Sample Input 2

2 2 0.05

Sample Output 2

3.6885245902

Explanation

Sample 0 

It may be surprising but any value of ${r}$ would give the same answer.
With probability $0.5$ there will be two dances only.
With probability ${0.25}$ there will be three dances (the course will end in one day or two days but we don't care about it).
With probability ${0.125}$ there will be four dances, and so on.
The expected value of the numbers of dances is exactly $3.{0}$.

Sample 1 

There are 2 boys and 3 girls.
There are 6 possible pairs and for each new dance each pair has probability $\frac{1}{6}$ to be chosen.
Let's name boys $\begin{array}{c}B_1\end{array}$ and $B_2$.
Similarly, let's name girls $G_1$, $G_2$, $G_3$.
One of possible scenarios is:

Day 0

$\begin{array}{c}B_1\end{array}$ and $G_2$ are chosen (probability $\frac{1}{6}$). They dance together.
$\begin{array}{c}B_1\end{array}$ and $G_1$ are chosen (prob. $\frac{1}{6}$). They dance.
$\begin{array}{c}B_1\end{array}$ and $G_2$ are chosen (prob. $\frac{1}{6}$). They have already danced on that day. Unfortunately, they get upset about it (prob. $r={0.075}$) and they don't dance now.

Day 1

A new day starts. $B_2$ and $G_3$ are chosen (prob. $\frac{1}{6}$). They dance.
$\begin{array}{c}B_1\end{array}$ and $G_2$ are chosen (prob. $\frac{1}{6}$). They dance. Note that it's not relevant what they did on the previous day.
$B_2$ and $G_3$ are chosen (prob. $\frac{1}{6}$). They have already danced on that day but they don't get upset about it (prob. $1-r=0.925$). They dance.
$\begin{array}{c}B_1\end{array}$ and $G_1$ are chosen (prob. $\frac{1}{6}$). They dance. Each person has danced on that day. The classes end.

There were 6 dances. The probability of the given scenario is $0.075\cdot0.925\cdot\left(\frac16\right)^6$

Technical note:

In this problem using a Run Code button will run your program only for the sample case 0. If you want to run others, run them as custom input.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Probability


Solutions:
from collections import defaultdict

def appsparsemat(mat, vec):
	toret = defaultdict(lambda : 0.0)
	for x in mat.keys():
		for y in mat[x].keys():
			toret[x] += mat[x][y] * vec[y]
	return toret
[b, g, r] = input().split()
b = int(b)
g = int(g)
r = float(r)
mat = defaultdict(lambda : defaultdict(lambda : 0.0))
avedancep = defaultdict(lambda : 0.0)
avedancee = defaultdict(lambda : 0.0)
avedancep[1, 1] = 1.0
avedancee[1, 1] = 0.0
succp = 0.0
succe = 0.0
failp = 0.0
faile = 0.0
for k in range(1, b * g + 1):
	nextavep = defaultdict(lambda : 0.0)
	nextavee = defaultdict(lambda : 0.0)
	for (i, j) in avedancep.keys():
		currp = avedancep[i, j]
		curre = avedancee[i, j]
		if i == b and j == g:
			succp += avedancep[i, j]
			succe += avedancee[i, j]
			continue
		extra = b * g / (b * g - k + k * r)
		if i < b and j < g:
			nextstate = (i + 1, j + 1)
			transprob = (b - i) * (g - j) / (b * g - k + k * r)
			nextavep[nextstate] += currp * transprob
			nextavee[nextstate] += curre * transprob + currp * transprob * extra
		if i < b:
			nextstate = (i + 1, j)
			transprob = (b - i) * j / (b * g - k + k * r)
			nextavep[nextstate] += currp * transprob
			nextavee[nextstate] += curre * transprob + currp * transprob * extra
		if j < g:
			nextstate = (i, j + 1)
			transprob = i * (g - j) / (b * g - k + k * r)
			nextavep[nextstate] += currp * transprob
			nextavee[nextstate] += curre * transprob + currp * transprob * extra
		nextstate = (i, j)
		transprob = (i * j - k) / (b * g - k + k * r)
		nextavep[nextstate] += currp * transprob
		nextavee[nextstate] += curre * transprob + currp * transprob * extra
		transprob = k * r / (b * g - k + k * r)
		failp += currp * transprob
		faile += curre * transprob + currp * transprob * extra
	succp += nextavep[b, g]
	succe += nextavee[b, g]
	nextavep.pop((b, g))
	nextavee.pop((b, g))
	avedancep = nextavep
	avedancee = nextavee
print(1.0 + (succe + faile) / succp)


from collections import defaultdict

def appsparsemat(mat, vec):
	toret = defaultdict(lambda : 0.0)
	for x in mat.keys():
		for y in mat[x].keys():
			toret[x] += mat[x][y] * vec[y]
	return toret
[b, g, r] = input().split()
b = int(b)
g = int(g)
r = float(r)
mat = defaultdict(lambda : defaultdict(lambda : 0.0))
avedancep = defaultdict(lambda : 0.0)
avedancee = defaultdict(lambda : 0.0)
avedancep[1, 1] = 1.0
avedancee[1, 1] = 0.0
succp = 0.0
succe = 0.0
failp = 0.0
faile = 0.0
for k in range(1, b * g + 1):
	nextavep = defaultdict(lambda : 0.0)
	nextavee = defaultdict(lambda : 0.0)
	for (i, j) in avedancep.keys():
		currp = avedancep[i, j]
		curre = avedancee[i, j]
		if i == b and j == g:
			succp += avedancep[i, j]
			succe += avedancee[i, j]
			continue
		extra = b * g / (b * g - k + k * r)
		if i < b and j < g:
			nextstate = (i + 1, j + 1)
			transprob = (b - i) * (g - j) / (b * g - k + k * r)
			nextavep[nextstate] += currp * transprob
			nextavee[nextstate] += curre * transprob + currp * transprob * extra
		if i < b:
			nextstate = (i + 1, j)
			transprob = (b - i) * j / (b * g - k + k * r)
			nextavep[nextstate] += currp * transprob
			nextavee[nextstate] += curre * transprob + currp * transprob * extra
		if j < g:
			nextstate = (i, j + 1)
			transprob = i * (g - j) / (b * g - k + k * r)
			nextavep[nextstate] += currp * transprob
			nextavee[nextstate] += curre * transprob + currp * transprob * extra
		nextstate = (i, j)
		transprob = (i * j - k) / (b * g - k + k * r)
		nextavep[nextstate] += currp * transprob
		nextavee[nextstate] += curre * transprob + currp * transprob * extra
		transprob = k * r / (b * g - k + k * r)
		failp += currp * transprob
		faile += curre * transprob + currp * transprob * extra
	succp += nextavep[b, g]
	succe += nextavee[b, g]
	nextavep.pop((b, g))
	nextavee.pop((b, g))
	avedancep = nextavep
	avedancee = nextavee
print(1.0 + (succe + faile) / succp)


import sys
numbers = input().split()
(n, m) = map(int, numbers[:2])
r = float(numbers[2])
states = {(0, 0, k): (0, 0) for k in range(max(n, m), n * m + 1)}
for s in range(1, n + m - 1):
	i = max(s - (m - 1), 0)
	while i < n and 0 <= s - i < m:
		j = s - i
		for k in reversed(range(max(n - i, m - j), (n - i) * (m - j) + 1)):
			(a, b) = (1, k / (n * m) * r)
			if (i - 1, j - 1, k + 1) in states:
				(a0, b0) = states[i - 1, j - 1, k + 1]
				c = i / n * j / m
				a += c * a0
				b += c * b0
			if (i - 1, j, k + 1) in states:
				(a0, b0) = states[i - 1, j, k + 1]
				c = i / n * (1 - j / m)
				a += c * a0
				b += c * b0
			if (i, j - 1, k + 1) in states:
				(a0, b0) = states[i, j - 1, k + 1]
				c = (1 - i / n) * j / m
				a += c * a0
				b += c * b0
			if (i, j, k + 1) in states:
				(a0, b0) = states[i, j, k + 1]
				c = ((n - i) * (m - j) - k) / (n * m)
				a += c * a0
				b += c * b0
			a /= 1 - k / (n * m) * (1 - r)
			b /= 1 - k / (n * m) * (1 - r)
			states[i, j, k] = (a, b)
		i += 1
(a, b) = states[n - 1, m - 1, 1]
print(f'{a / (1 - b) + 1}')