每当彼得感到无聊时，他就会把一些碗围成一圈，每个碗里装一粒豆子。之后，他将所有豆子从某个碗中取出，并按顺时针方向将它们一颗一颗地放入碗中。他重复这一过程，从最后一颗豆子放入的碗开始，直到最初的情况再次出现。例如，对于 5 个碗，他的行为如下：

因此，对于 $5$ 的碗，Peter 需要移动 $15$ 才能回到初始状态。

让 $M(x)$ 表示返回初始状态所需的移动次数，从 $x$ 碗开始。因此，$M(5)=15$。还可以验证 $M(100)=10920$。

求 ${\displaystyle \sum _{k=0}^{{10}^{18}}M(2^k+1)}$。以 $7^9$ 为模给出你的答案。