How Many Seeds to Plant?

A gardener sows rare seeds in a pot. Each seed sprouts with probability p, independently of the others. How many seeds must go into the pot so that the probability that at least one of them sprouts is at least goal?

Both p and goal are given as fractions (numerator, denominator). Write seeds_needed(p, goal) that returns a tuple (k, chance): the smallest number of seeds k for which the probability of at least one sprout is >= goal, and that probability as a float.

The comparison with goal must be exact: in some tests the probability for the right k is exactly equal to goal, and floating-point rounding would make it look a tiny bit smaller.

Examples

Input:  p = (1, 4), goal = (9, 10)
Output: (9, 0.9249153137207031)
Explanation: with k seeds, P(none sprouts) = (3/4)^k. For k = 8 the chance of at least one
is 1 - 0.1001 = 0.8999, just short of 0.9; for k = 9 it is 1 - 0.0751 = 0.9249.

Input:  p = (1, 10), goal = (271, 1000)
Output: (3, 0.271)
Explanation: 1 - (9/10)^3 = 1 - 729/1000 = 271/1000 exactly, so 3 seeds are enough.

Constraints

• 1 <= numerator <= denominator <= 100 for p
• 0 <= numerator < denominator <= 10000 for goal, so goal < 1
• floats are compared with a tolerance of 1e-6

Goals

• Turn "at least one" into "not none" with the complement rule
• Multiply the probabilities of independent failures
• Compare probabilities exactly, without floating-point rounding