OMC094(E)

点数: 600

Writer: idtwstaos

　$4×4$ のマス目があり, 以下の要領でそれぞれのマスに一つずつ数を書き込みます. ここで, 上から $i$ 行目, 左から $j$ 列目（$i,j$ は $1$ 以上 $4$ 以下の整数）に書き込まれる数を $a_{ij}$ で表します.

• まず, $1$ 行目または $1$ 列目にある $7$ マスに $1$ 以上 $7$ 以下の相異なる整数をそれぞれ $1$ 回ずつ書き込む.
• 続いてそれ以外のマス（上から $i$ 行目, 左から $j$ 列目）に, 以下を常にみたすように数を書き込む. $$a_{ij}=\max\big\{\gcd(a_{i-1,j-1},a_{i,j-1}), ~ \gcd(a_{i-1,j-1},a_{i-1,j}), ~ \gcd(a_{i,j-1},a_{i-1,j})\big\}$$

　このとき, 最終的な数の書き込まれ方は $7!$ 通り存在しますが, それらすべてについての $a_{44}$ の（相加）平均を求めてください. ただし, 求める値は互いに素な正整数 $a, b$ を用いて $\dfrac{a}{b}$ と表されるので, $a+b$ を解答してください.