335 : 豆集め

ピーターは退屈するといつも, 何枚かボウルを円状に置き, １個ずつ豆を入れる. 次に, ある１枚のボウルから豆をすべて取り出し, 時計回りにボウルに１個ずつ落とし入れていく. 最後の豆を落とし入れたボウルから始めて, 最初の状況が再び現れるまでこれを繰り返す. 例えば５枚のボウルでは次のように動かす：

p335_mancala.gif

したがって５枚のボウルではピーターは最初の状況に戻るのに 15 手かかる.$x$枚のボウルから始めて, 最初の状況に戻るのに必要な手の数を$M(x)$と表そう. ゆえに$M(5) = 15$である. また$M(100) = 10920$であることが確かめられる.

$\displaystyle \sum_{k=0}^{10^{18}} M(2k+1)$を求めよ. 答えを$\mod 7^9$で入力せよ.