反复抛掷一枚无偏向的硬币，直到获得连续两个正面。假设这些发生在第 $(M-1)$ 次和第 $M$ 次抛掷中。
令 $P(n)$ 为 $M$ 能被 $n$ 整除的概率。例如，结果 HH、HTHH 和 THTTHH 都计入 $P(2)$，但 THH 和 HTTHH 则不计入。

已知 $P(2)=\frac{3}{5}$ 和 $P(3)=\frac{9}{31}$。事实上，可以证明 $P(n)$ 始终是一个有理数。

对于质数 $p$ 和完全约简分数 $\frac{a}{b}$，定义 $Q(\frac{a}{b},p)$ 为最小正 $q$，其中 $a\equiv bq(\mathrm{mod}p)$。
例如 $Q(P(2),109)=Q(\frac{3}{5},109)=66$，因为 $5\cdot 66=330\equiv 3(\mathrm{mod}109)$ 和 $66$ 是此类数字的最小正数。
同样$Q(P(3),109)=46$。

求 $Q(P({10}^{18}),1000000009)$。