OMC026(E)

点数: 600

Writer: Nijata

　$10^7$ 行 $10^7+1$ 列のマス目があり, 最も左下の頂点と最も右上の頂点を結ぶ直線を $\ell$ とします. いま, 各列についてちょうど $1$ マスを黒く塗り, 隣り合う列の黒いマスの中心を線分で結ぶことで折れ線 $\ell^{\prime}$ を作ります. このとき, すべての黒マスの塗り方 $10^{7(10^7+1)}$ 通りについて, $\ell$ と $\ell^{\prime}$ の共有点の個数の平均を求めてください.
　ただし, 答えは互いに素な正整数 $p,q$ によって $\dfrac{p}{q}$ と表せるので, $p+q$ を解答してください.
　ここで, マスはすべて正方形とし, 各マスの中心を正方形の対角線の交点として定めます.