Каждый раз, когда Питеру становится скучно, он расставляет в круг несколько мисок, в каждой из которых лежит один боб. После этого он берет бобы из определенной миски и кладет их по одному в следующие миски, продвигаясь по часовой стрелке. Он повторяет процесс, начиная с миски, в которую он бросил последний боб, до тех пор, пока не получит исходное положение мисок. Например, в случае с 5 мисками, он действует следующим образом:

Таким образом, с 5 мисками Питеру потребовалось совершить 15 ходов, чтобы вернуться в исходное положение.

Пусть M(x) - число ходов, необходимое для того, чтобы вернуться в исходное положение для x мисок. Таким образом, M(5) = 15. Можно убедиться, что M(100) = 10920.

Найдите M(2^k+1). Ответ приведите по модулю 7⁹.