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: interview

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