OMC032(E)

点数: 700

Writer: simasima

　魔王・死魔死魔に敗れた勇者・しおしおの飛ばされた異世界では, 将棋のルールに草将という駒が追加されていました. この駒は, 以下に示された $6$ マスのいずれかに $1$ 手で移動できます.

　$10^{1341398}\times 10^{1341398}$ の正方形状のマス目があり, そのうちいくつかのマスを黒く塗ります. どの黒マスに草将を置いても, 他の黒マスへ草将が $2358$ 手以内に移ることができない状態を「草cial distance」が保たれていると呼ぶことにします.
　しおしおは「草cial distance」を保ったまま黒マスを出来るだけたくさん塗りたいです. このとき, マス全体に占める黒マスの割合を $x$ とおきます. 分母が $10^{20}$ 以下の正整数であるような既約分数であって, $x$ 以下で最大のもの $p$ について, その分母と分子の和を求めてください.