---

Problem 335

---

Gathering the beans

Whenever Peter feels bored, he places some bowls, containing one bean each, in a circle. After this, he takes all the beans out of a certain bowl and drops them one by one in the bowls going clockwise. He repeats this, starting from the bowl he dropped the last bean in, until the initial situation appears again. For example with 5 bowls he acts as follows:

So with 5 bowls it takes Peter 15 moves to return to the initial situation.

Let M(x) represent the number of moves required to return to the initial situation, starting with x bowls. Thus, M(5) = 15. It can also be verified that M(100) = 10920.

Find $\sum_{k=0}^{10^{18}}$M(2^k+1). Give your answer modulo 7⁹.

---

收豆子

每当彼得感到无聊的时候，他会将一些碗摆成圆形，每个碗中放一颗豆子。然后，他拿出某一个碗中的所有豆子，把这些豆子按顺时针在每个碗中放一个，再从最后放入豆子的那个碗开始重复这一操作，直到回到初始状态。例如，当有5个碗时，他每一次的操作如下所示：

因此，有5个碗时，彼得需要15次操作，才能回到初始状态。

记M(x)为当有x个碗时，回到初始状态所需要的操作数。因此，M(5) = 15。同样可以验证M(100) = 10920。

求$\sum_{k=0}^{10^{18}}$M(2^k+1)。将你的答案模7⁹取余。

---