Рома завел нового персонажа в игре «World of Darkraft - 2». В игре персонаж сражается с монстрами, приобретает все более и более продвинутое снаряжение, что позволяет в свою очередь сражаться с более сильными монстрами.

Персонаж может экипироваться вещами k различных типов. Сила каждой вещи характеризуется целым положительным числом — ее уровнем. Изначально персонаж имеет по одной вещи уровня 1 каждого из k типов.

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

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

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