Stacey is a big [AD&D](https://en.wikipedia.org/wiki/Dungeons_%26_Dragons) games nerd. Moreover, she's a munchkin. Not a [cat breed](https://en.wikipedia.org/wiki/Munchkin_cat), but a person who likes to get maximum efficiency of their character.

As you might know, many aspects of such games are modelled by rolling dice and checking it against a threshold value determined by various aspects.
Stacey wants to always control the situation and know whether she can beat the foe with certain special ability or not. Unfortunately she doesn't know probabilty theory well enough. Help Stacey by providing a calculating utility for her.

P.S.: Stacey says that she has tried to implement a calculator by Monte-Carlo modelling: calling rand() in a loop, but she hasn't been satisfied with precision of this method.

### Examples

`P(1d6 >= 4)` means the chance of getting 4 points or higher on a regular cubic die. Obviously the chance is `3/6` cause there're 6 possibilities in total (1, 2, 3, 4, 5, 6) and only three of them are >= 4: (4, 5, 6)

`P(2d6 >= 3)` gives us `35/36`, cause the only possibility to get < 3 is rolling exactly 1+1.
Exactly 2 as sum of two dice appears only if both have 1. While total amount of different outcomes is 6\*6 = 36. Hence resulting probability is 1-1/36, which is 35/36

### Your task

is to write a function, which will calculate the probability of that a die with `N` sides rolled `M` times (`MdN` in AD&D notation) will get at least `T` points. We don't add modifiers cause they are already incorporated into the threshold.

Input arguments will be valid integers with the following limits:

- `rolls` 1..20
- `sides` 2..100
- `threshold` 1..2000

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Probability

Starter code:
def roll_dice (rolls, sides, threshold):
	

Solutions:
def roll_dice(rolls, sides, threshold):
	dp = [0] * (rolls * sides + 1)
	for i in range(1, sides + 1):
		dp[i] = 1
	for _ in range(rolls - 1):
		for x in range(rolls * sides, 0, -1):
			dp[x] = sum(dp[max(1, x - sides):x])
	return sum(dp[threshold:]) / sum(dp[1:])


c = [[1]]
p = [1, 1]
c.append(p)
for i in range(1, 2100):
	a = [1]
	for j in range(1, i + 1):
		a.append(p[j - 1] + p[j])
	a.append(1)
	c.append(a)
	p = a

def roll_dice(rolls, sides, threshold):
	if threshold <= rolls:
		return 1
	if threshold > rolls * sides:
		return 0
	threshold -= rolls + 1
	sum_ = 0.0
	i = 0
	while threshold >= 0:
		sum_ += (-1) ** i * c[rolls][i] * c[threshold + rolls][threshold]
		threshold -= sides
		i += 1
	return 1.0 - sum_ / sides ** rolls


def roll_dice(rolls, sides, threshold):
	divisor = sides ** rolls
	stack = [1 for i in range(sides)]
	for i in range(1, rolls):
		nstack = [0 for j in range(len(stack) + sides - 1)]
		for j in range(len(nstack)):
			start = j - sides + 1
			if start < 0:
				start = 0
			end = j
			if end >= len(stack):
				end = len(stack) - 1
			nstack[j] = sum(stack[start:end + 1])
		stack = nstack
	divend = sum(stack[threshold - rolls:])
	return divend / divisor


from scipy.misc import comb

def Comb(c, n, k):
	if c[n][k]:
		return c[n][k]
	c[n][k] = comb(n, k)
	return c[n][k]

def P(C_vect, p, n, s):
	return sum(((-1) ** k * Comb(C_vect, n, k) * Comb(C_vect, p - s * k - 1, n - 1) for k in range((p - n) // s + 1))) / s ** n

def roll_dice(rolls, sides, threshold):
	if threshold > sides * rolls:
		return 0
	if threshold == sides ** rolls:
		return 1 / sides ** rolls
	if threshold <= rolls:
		return 1
	k_max = max((threshold - rolls) // sides, rolls - 1)
	n_max = max(sides, threshold - 1)
	C_vect = [[0 for _ in range(k_max + 1)] for _ in range(n_max + 1)]
	inv_prob = 0
	for t in range(rolls, threshold):
		inv_prob += P(C_vect, t, rolls, sides)
	return 1 - inv_prob


from math import *

def roll_dice(rolls, sides, threshold):
	total = sides ** rolls
	(f1, f2, outcomes) = (1, 1, 0)
	for j in range(rolls, min(threshold, rolls * sides - threshold + rolls + 1)):
		k = (j - rolls) // sides
		f1 = 1
		for i in range(0, k + 1):
			f1 = factorial(rolls) // (factorial(i) * factorial(rolls - i))
			f2 = factorial(j - sides * i - 1) // (factorial(j - sides * i - rolls) * factorial(rolls - 1))
			outcomes += (-1) ** i * f1 * f2
	if threshold > sides * rolls:
		return 0.0
	elif threshold <= rolls * sides - threshold + rolls + 1:
		return 1 - outcomes / total
	else:
		return outcomes / total


memo = {}

def roll_dice(rolls, sides, threshold):
	memo = {}
	r = 0
	for i in range(rolls, threshold):
		r += _roll_dice(rolls, sides, i)
	return 1 - r

def _roll_dice(rolls, sides, s):
	if s < 1:
		return 0
	elif rolls == 1:
		if s > sides:
			return 0
		return 1 / sides
	key = (rolls, sides, s)
	if key in memo:
		return memo[key]
	r = 0
	for i in range(1, sides + 1):
		r += _roll_dice(rolls - 1, sides, s - i)
	memo[key] = r / sides
	return r / sides