The birthday problem

How many people does it take before two of them probably share a birthday? Fewer than most people guess.

What to build

A program that prints the chance that at least two of n people share a birthday.

Requirements

  • Assume 365 equally likely birthdays and independent people. Print the probability that at least two share a birthday, to 4 decimal places.

Input

One whole number n.

Output

One line.

Constraints

1 ≤ n ≤ 400.

Example

Input:

23

Output:

0.5073

Why it works

"At least two share" is the complement of "all different", and all different is a product of shrinking chances, which falls below one half at only 23 people.

Examples

Example 1 · Input
23
Expected output
0.5073
Example 2 · Input
10
Expected output
0.1169

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

Hints

Hint 1

Find the chance that all n birthdays are different, then use the complement.

Hint 2

The k-th person must avoid the k − 1 days already taken: (365 − (k − 1)) ÷ 365.

Solution

Show one correct solution (try it yourself first)
n = int(input())
all_different = 1.0
for k in range(n):
    all_different *= (365 - k) / 365
print(f"{1 - all_different:.4f}")

Lesson: Rules: not, or, and →