CF464D.World of Darkraft - 2

Roma found a new character in the game "World of Darkraft - 2". In this game the character fights monsters, finds the more and more advanced stuff that lets him fight stronger monsters.

The character can equip himself with k distinct types of items. Power of each item depends on its level (positive integer number). Initially the character has one 1-level item of each of the k types.

After the victory over the monster the character finds exactly one new randomly generated item. The generation process looks as follows. Firstly the type of the item is defined; each of the k types has the same probability. Then the level of the new item is defined. Let's assume that the level of player's item of the chosen type is equal to t at the moment. Level of the new item will be chosen uniformly among integers from segment [1; t + 1].

From the new item and the current player's item of the same type Roma chooses the best one (i.e. the one with greater level) and equips it (if both of them has the same level Roma choses any). The remaining item is sold for coins. Roma sells an item of level x of any type for x coins.

Help Roma determine the expected number of earned coins after the victory over n monsters.

罗玛在游戏《暗黑世界2》中发现了一个新角色。在这个游戏中，角色与怪物战斗，并不断获得越来越高级的装备，从而能够对抗更强大的怪物。

角色可以装备 $k$ 种互不相同的物品。每件物品的威力取决于其等级（正整数）。初始时，角色拥有每种类型的物品各一件，且等级均为 $1$。

每次击败一个怪物后，角色会恰好获得一件新生成的随机物品。生成过程如下：首先确定该物品的类型，$k$ 种类型被选中的概率均等；然后确定该新物品的等级。假设此时角色所拥有的该类型物品的等级为 $t$，则新物品的等级将在区间 $[1,\,t+1]$ 中的整数中均匀随机选取。

接着，罗玛从这件新物品和角色当前拥有的同类型物品中，选择等级更高者进行装备（若两者等级相同，则任选其一）；另一件则出售换取金币。罗玛出售任意类型、等级为 $x$ 的物品可获得 $x$ 枚金币。

请帮助罗玛计算：在击败 $n$ 个怪物后，所获得金币总数的期望值。

The first line contains two integers, n and k (1 ≤ n ≤ 105; 1 ≤ k ≤ 100).

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^5$；$1 \leq k \leq 100$）。

Print a real number — expected number of earned coins after victory over n monsters. The answer is considered correct if its relative or absolute error doesn't exceed 10 - 9.

输出一个实数——击败 n 个怪物后获得的金币数的期望值。若答案的相对误差或绝对误差不超过 $10^{-9}$，则视为正确。