Expected Marked Leaves in a Randomized Lazy Propagation Segment Tree

Bob loves segment trees. In this problem, Bob considers a generalized segment tree with the root covering the interval \([1, n]\). In a generalized segment tree the splitting point \(m\) in a node covering \([l, r]\) can be chosen arbitrarily as long as \(l \le m < r\). Therefore, the depth of the tree can be as large as \(O(n)\).

Bob will perform \(k\) operations. In each operation, he selects uniformly at random one of the \(\frac{n(n+1)}{2}\) subintervals \([l, r]\) from \([1, n]\) (each subinterval is chosen with equal probability). Then he executes the following update procedure starting from the root:

MODIFY(node, L, R, l, r):
    // The current node covers the interval [L, R]
    if ([l, r] completely covers [L, R]) then
        if (L == R) {  // leaf node
            mark this node permanently (i.e. tag[node] = 1);
        } else {       // non-leaf node
            push the lazy tag down to its children;
        }
    else
        recursively call MODIFY on the children as necessary

Note that once a leaf node (i.e. an interval of the form \([i, i]\)) gets marked, the mark remains forever. Non-leaf nodes never permanently maintain a mark because if they are updated they push the lazy mark down immediately. You may also interpret the process as follows: Initially, all nodes have a tag value of \(0\). Bob performs \(k\) operations. In each operation, he randomly selects an interval \([l, r]\) among all \(\frac{n(n+1)}{2}\) possibilities and calls MODIFY(root, 1, n, l, r); The final answer is the expected number of nodes in the entire segment tree having a tag value of \(1\).

Because only the leaf nodes (which correspond to the single indices \(i = 1, 2, \dots, n\)) can retain the mark, the answer reduces to computing the expected number of leaves that are marked after \(k\) operations.

For a fixed leaf corresponding to index \(i\), note that in an update operation the leaf will be visited (and thus marked) if and only if the randomly chosen update interval \([l, r]\) contains \(i\). The number of subintervals that contain \(i\) is \(i \times (n - i + 1)\) and the total number of subintervals is \(\frac{n(n+1)}{2}\). Thus, the probability \(p_i\) that a given operation marks leaf \(i\) is: \[ p_i = \frac{2i(n-i+1)}{n(n+1)}. \]

Since operations are independent, the probability that leaf \(i\) never gets marked in any of the \(k\) operations is \((1-p_i)^k\) and the probability that it is marked at least once is \(1-(1-p_i)^k\). Therefore, the expected number of marked leaves is: \[ E = \sum_{i=1}^{n}\left(1 - (1-p_i)^k\right) = \sum_{i=1}^{n}\left(1 - \left(1 - \frac{2i(n-i+1)}{n(n+1)}\right)^k\right). \]

Your task is to compute and output the expected number of marked leaves.

inputFormat

The input consists of a single line containing two integers \(n\) and \(k\) \( (1 \leq n, k \leq 10^5)\), where \(n\) is the length of the segment covered by the root and \(k\) is the number of operations.

outputFormat

Output a single real number which is the expected number of marked leaves. The answer will be accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

3 1

1.6666666667