OMC032(D)

点数: 600

Writer: simasima

　sima姉妹は $6\times10^8$人の女子からなり, 生まれが早い方から $1\text{子},2\text{子},\cdots,6\times10^8$ 子と名付けられています. ここで各人の生年月日は異なるものとします. 各 $x=1,2\cdots,6\times10^8-1$ の順に, $x$ 子が以下の操作を行います.

• 自分の妹 $(6\times10^8-x)$ 人から等確率に一人を選び, $(\text{今まで自分が撫でられた回数}+x^2)回$ 撫でる.

このとき $3\times10^8+8$ 子が撫でられる回数の期待値を求めてください.
　ただし, 答えは互いに素な正整数 $a,b$ によって $\dfrac{a}{b}$ と表されるので, $a+b$ を $10^{12}$ で割った余りを解答してください.