Подскажите, пожалуйста, как тут посчитать правильно:

Один любитель азартных игр постоянно проигрывал в игровых автоматах. Он попросил своего приятеля-программиста разработать ему программу для КПК, которая помогла бы ему в оценке шансов в играх.

Входными данными должны быть два числа: N – максимальное число ходов в игре и М – число равновероятных исходов при одном ходе. (Например, при М = 6 получаем игру с кубиком, при М = 13 – с волчком как в игре «Что? Где? Когда?» и т.д.). Все исходы занумерованы от 1 до M. После любого хода (вплоть до N, когда игра сама закончится) игрок может остановиться, и результатом игры в этом случае** будет номер последнего исхода**. Нужно определить математическое ожидание результата игры при оптимальной стратегии играющего, то есть стратегии, которая максимизирует это математическое ожидание.

(N, M <= 100)

UPD: задача с West Siberian Subregional Contest 2011