Lottery: matching exactly m numbers

A lottery draws k different numbers from 1 to n, and you hold a ticket of k numbers. Work out the chance of matching exactly m of them.

What to build

A program that prints the probability of exactly m matches and the odds against it.

Requirements

  • Print P(match M) = F with F a reduced fraction (0 when impossible).
  • Then print odds 1 in X, where X is the number of tickets divided by the favourable ones, rounded to the nearest whole number, or odds impossible when no draw gives m matches.

Input

One line: n, k and m.

Output

Two lines.

Constraints

1 ≤ k ≤ n ≤ 60; 0 ≤ m ≤ k.

Example

Input:

49 6 6

Output:

P(match 6) = 1/13983816
odds 1 in 13983816

Why it works

Every draw of k numbers is equally likely; the favourable draws pick m of your numbers and the rest from the numbers you did not choose, so the count is a product of two combinations.

Examples

Example 1 · Input
49 6 6
Expected output
P(match 6) = 1/13983816
odds 1 in 13983816
Example 2 · Input
10 3 1
Expected output
P(match 1) = 21/40
odds 1 in 2

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Choose which m of your k numbers match, and which k − m of the other n − k numbers fill the draw.

Hint 2

P = C(k, m) × C(n − k, k − m) ÷ C(n, k); keep it as a Fraction.

Solution

Show one correct solution (try it yourself first)
from fractions import Fraction
from math import comb

n, k, m = map(int, input().split())
total = comb(n, k)
good = comb(k, m) * comb(n - k, k - m)
print(f"P(match {m}) = {Fraction(good, total)}")
print("odds impossible" if good == 0 else f"odds 1 in {round(total / good)}")

Lesson: Counting outcomes: permutations and combinations →