Світ Даркрафта - 2

Рома завів нового персонажа в грі «World of Darkraft - 2». У цій грі персонаж бореться з монстрами, здобуваючи все більш просунуте спорядження, що дозволяє йому змагатися з сильнішими монстрами.

Персонаж може екіпіруватися речами $k$ різних типів. Сила кожної речі визначається цілим додатним числом — її рівнем. Спочатку персонаж має по одній речі рівня $1$ кожного з $k$ типів.

Після перемоги над монстром персонаж знаходить рівно одну нову річ, яка генерується випадковим чином. Спочатку визначається тип нової речі; кожен з $k$ типів має однакову ймовірність. Потім визначається рівень нової речі; нехай рівень речі обраного типу, яка є у гравця в даний момент, дорівнює $t$. Тоді рівень нової речі буде обраний рівноймовірно серед цілих чисел з відрізка [1; t + 1].

З нової речі та речі того ж типу, яка є у нього в даний момент, Рома обирає кращу (тобто річ з більшим рівнем) та екіпірується нею, а залишену продає торговцю за монети (якщо обидві речі мають однаковий рівень, то Рома екіпірується будь-якою з них). За річ рівня $x$ будь-якого типу торговець платить Ромі $x$ монет.

Допоможіть Ромі визначити математичне сподівання кількості зароблених монет після перемоги над $n$ монстрами.