Nobody Draws Their Own Name

An office of n people runs a gift draw: all n names go into a hat, it is shaken, and each person draws one name. The draw has to be repeated if somebody draws their own name. How likely is a draw that works first time?

Write secret_santa(n, trials, seed) that returns a tuple (estimate, exact):

• estimate: simulate trials draws. Create one generator rng = random.Random(seed). For each draw, start from hat = list(range(n)), call rng.shuffle(hat) once, and let person i draw hat[i]. The draw works when hat[i] != i for every i. estimate is the fraction of draws that work, as a float.
• exact: the exact probability as a tuple (numerator, denominator) in lowest terms ((0, 1) for probability 0). All orderings of the names are equally likely.

Examples

Input:  n = 3, trials = 1000, seed = 1
Output: (0.329, (1, 3))
Explanation: of the 6 orderings of 0 1 2, only 1 2 0 and 2 0 1 give nobody their own
name, so the exact probability is 2/6 = 1/3. The simulation found 329 good draws in 1000.

Input:  n = 4, trials = 2000, seed = 2
Output: (0.372, (3, 8))

Constraints

• 1 <= n <= 8, 1 <= trials <= 20000
• 0 <= seed < 2**32; the result must not depend on the clock or on other randomness
• floats are compared with a tolerance of 1e-6

Goals

• Estimate a probability by a seeded simulation that follows stated rules
• Compute the same probability exactly by counting equally likely orderings
• Compare the estimate with the exact answer