Treap ambiguity P30477

Roughly speaking, a treap is a BST (a binary search tree) and also a heap. Assume that we have $n$ different keys, and a fixed integer $m$. Every key is independently associated with a priority (a random integer chosen uniformly from the interval $[1, m]$). Let $x$ be the key with the largest priority. Then, the treap for the set of pairs (key, priority) is the BST with $x$ at its root, the treap for the pairs with keys smaller than $x$ as its left subtree, and the treap for the pairs with keys larger than $x$ as its right subtree.

For instance, suppose that the keys are $\{ 40, 41, 42, 49, 70, 80 \}$ and $m = 1000$. Then, the pairs (key, priority) could be (40, 189), (41, 350), (42, 960), (49, 234), (70, 800) and (80, 780). In this case, we would have the treap to the left:

$$\pstree[levelsep=40pt,treesep=30pt]{\Tcircle{\mbox{\color{blue} \scriptsize 42} \, \mbox{\color{red} \tiny (960)}}}{ \pstree{\Tcircle{\mbox{\color{blue} \scriptsize 41} \, \mbox{\color{red} \tiny (350)}}} { \pstree{\Tcircle{\mbox{\color{blue} \scriptsize 40} \, \mbox{\color{red} \tiny (189)}}} {} \Tn } \pstree{\Tcircle{\mbox{\color{blue} \scriptsize 70} \, \mbox{\color{red} \tiny (800)}}} { \pstree{\Tcircle{\mbox{\color{blue} \scriptsize 49} \, \mbox{\color{red} \tiny (234)}}} {} \pstree{\Tcircle{\mbox{\color{blue} \scriptsize 80} \, \mbox{\color{red} \tiny (780)}}} {} } } \enspace \pstree[levelsep=40pt,treesep=30pt]{\Tcircle{\mbox{\color{blue} \scriptsize 3} \, \mbox{\color{red} \tiny (42)}}}{ \Tn \pstree{\Tcircle{\mbox{\color{blue} \scriptsize 5} \, \mbox{\color{red} \tiny (42)}}} {} } \qquad \pstree[levelsep=40pt,treesep=30pt]{\Tcircle{\mbox{\color{blue} \scriptsize 5} \, \mbox{\color{red} \tiny (42)}}}{ \pstree{\Tcircle{\mbox{\color{blue} \scriptsize 3} \, \mbox{\color{red} \tiny (42)}}} {} \Tn } \qquad \pstree[levelsep=40pt,treesep=30pt]{\Tcircle{\mbox{\color{blue} \scriptsize 3} \, \mbox{\color{red} \tiny (42)}}}{ \pstree{\Tcircle{\mbox{\color{blue} \scriptsize 2} \, \mbox{\color{red} \tiny (23)}}} {} \pstree{\Tcircle{\mbox{\color{blue} \scriptsize 5} \, \mbox{\color{red} \tiny (23)}}} {} }$$

If we only look at the keys (in blue), we have a BST. If we only look at the priorities (in red), we have a sort of a heap (the largest at the top; the same property holds recursively).

This definition is usually good enough in many practical situations. However, there is a caveat: With repeated priorities, we can have more than one possible treap. For example, the second and the third treaps above are possible for the pairs (3, 42) and (5, 42).

Note that we can have a unique treap with repeated priorities. Consider for instance the pairs (2, 23), (3, 42) and (5, 23). The only possible treap is the fourth above.

Given $n$ and $m$, what is the probability that the treap is unique?

Input

Input consists of several cases, each with $n$ and $m$. Assume $1 \le n \le 50$ and $2 \le m \le 5000$.

Output

For every case, print the probability that the treap is unique with four digits after the decimal point. The input cases have no precision issues.