Probability of Pairwise Isomorphic Trees

In this problem, a rooted tree with n nodes is generated using the following random process:

• Node 1 is the root.
• For every i with 2 ≤ i ≤ n, a parent is chosen uniformly at random from the nodes 1, 2, …, i-1.

This produces an increasing tree (i.e. the labels increase along any branch from the root) and every possible increasing tree is generated with the same probability, namely 1/(n-1)! (with the convention that 0! = 1 when n = 1).

Let an isomorphism between two rooted trees be defined as follows: two trees T₁ and T₂ on n nodes are isomorphic if and only if there exists a permutation p of {1, 2, …, n} with p₁ = 1 such that for every node i (2 ≤ i ≤ n), if the parent of i in T₁ is f then the parent of p_i in T₂ is p_f. In other words, the tree structures are “the same” up to a renaming of the nodes that fixes the root.

Now, suppose we independently generate k trees T₁, T₂, …, T_k using the above process. Let I(T) be the number of increasing trees (i.e. the number of labeled trees obtained by the process) that have the same tree isomorphism type as T. Since the process generates each increasing tree with equal probability, the probability that a random tree has isomorphism type T is I(T)/(n-1)!.

Your task is to compute the probability that all k independently generated trees are pairwise isomorphic. In other words, if the isomorphism types (of the trees produced by the process) are T₁, T₂, …, then the answer is

$$P = \sum_{\text{isomorphism types }T}\Bigl(\frac{I(T)}{(n-1)!}\Bigr)^k. $$

Because the number of increasing trees for a fixed n is exactly (n-1)!, the denominator in the probability is ((n-1)!)^k and the numerator is the sum over all isomorphism types of I(T)^k.

Print the computed probability as a floating‐point number with 6 decimal places.

inputFormat

The input consists of a single line containing two integers n and k (with n ≥ 1 and k ≥ 1). When n = 1, the tree is just a single node.

outputFormat

Output the probability that k trees generated by the random process are pairwise isomorphic, formatted to 6 decimal places.

sample

3 2

0.500000