OMCE003(F)

点数: 700

Writer: Shota_1110

　三次元空間において，$x, y, z$ 座標がすべて整数であるような点を格子点と呼ぶことにします．次の条件をみたす格子点全体からなる集合を $\Omega$ とします：

• $x, y, z$ 座標のうち少なくとも二つは，$3$ で割ると $2$ 余る数である．

また，以下の $3$ 条件をすべてみたす格子点全体からなる集合を $\Gamma$ とします：

• $x$ 座標は $1$ 以上かつ $21$ 以下である．
• $y$ 座標は $1$ 以上かつ $33$ 以下である．
• $z$ 座標は $1$ 以上かつ $39$ 以下である．

ここで，$\Gamma$ から相異なる $1000$ 個の点を選ぶ方法であって，次の条件をみたすものの個数を $N$ とします：

• 選んだ $1000$ 点を $P_1, P_2, \ldots, P_{1000}$ としたとき，任意の $Q \in \Omega$ に対し $1000$ 個の線分 $P_1Q, P_2Q, \ldots, P_{1000}Q$ の中で長さが $2$ 未満のものは高々 $1$ 個である．

ただし点を選ぶ順序は区別しません．また両端点が一致する線分の長さは $0$ であるとします．
　このとき $N$ は，$p_1 \lt p_2 \lt \cdots \lt p_t$ なる $t$ 個の素数 $p_1, p_2, \ldots, p_t$ と $t$ 個の正整数 $n_1, n_2, \ldots, n_t$ によって $$N = p_1^{n_1} \times p_2^{n_2} \times \cdots \times p_t^{n_t}$$ と（一意的に）表せるので，$n_1 + n_2 + \cdots + n_t$ の値を解答して下さい．