　正整数 $n$ に対し $n$ 以下の正整数全体からなる集合を $[n]$ と書く．$X, Y, Z$ を正整数とし，一般に $\Gamma$ を次のように定める（問題の設定では $(X, Y, Z) = (7, 11, 13)$ である）．

- $\Gamma$ を $x \in [3X], y \in [3Y], z \in [3Z]$ なる格子点 $(x, y, z)$ からなる集合とする．

また，$\Omega$ の部分集合 $\Omega_x, \Omega_y, \Omega_z$ をそれぞれ次のように定める．なお，これらは $\Omega_x \cup \Omega_y \cup \Omega_z = \Omega$ をみたしている．
- $y, z$ 座標がともに $3$ で割ると $2$ 余るような格子点全体からなる集合を $\Omega_x$ とする．
- $z, x$ 座標がともに $3$ で割ると $2$ 余るような格子点全体からなる集合を $\Omega_y$ とする．
- $x, y$ 座標がともに $3$ で割ると $2$ 余るような格子点全体からなる集合を $\Omega_z$ とする．

ここで格子点の集合 $U$ と有限個の格子点の集合 $V$ に対し，$V$ が次の条件をみたすことを，「$V$ が条件 $\Lambda(U)$ をみたす」と呼ぶことにする．
- $V$ に属するすべての点を $P_1, P_2, ..., P_t$ としたとき，任意の $Q \in U$ に対し線分 $P_1Q, P_2Q, ..., P_tQ$ の中で長さが $2$ 未満のものは高々 $1$ 個である．

ここで補題を与える．

---

**補題 1.**　$P, Q$ を相異なる格子点としたとき，線分 $PQ$ の長さが $2$ 未満であるための必要十分条件は，$P, Q$ の座標をそれぞれ $(x_1, y_1, z_1), (x_2, y_2, z_2)$ としたときに $|x_1 - x_2|, |y_1 - y_2|, |z_1 - z_2|$ がすべて $1$ 以下となることである．

<details><summary>補題 1. の証明<\/summary>
　$|x_1 - x_2|, |y_1 - y_2|, |z_1 - z_2|$ がいずれも $1$ 以下のときは
$$PQ = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2} \leq \sqrt{3} \lt 2$$
が得られ，逆に $2$ 以上のものが存在すれば
$$PQ \geq \max \\{ |x_1 - x_2|, |y_1 - y_2|, |z_1 - z_2| \\} \geq 2$$
が得られる．
<\/details>

---

　それでは，$\Gamma$ の部分集合 $\gamma$ であって条件 $\Lambda(\Omega)$ をみたすものを考えよう．$i \in [X], j \in [Y], k \in [Z]$ に対し，集合 $B_{i, j, k}$ を次のように定める．
- $3i - 2 \leq x \leq 3i, 3j - 2 \leq y \leq 3j, 3k - 2 \leq z \leq 3k$ なる格子点 $(x, y, z)$ 全体の集合を $B_{i, j, k}$ とする．

すると $B_{i, j, k}$ は点 $(3i - 1, 3j - 1, 3k - 1)$ からの距離が $2$ 未満の格子点全体の集合に等しいことが，補題 1. からわかる．また $XYZ$ 個の集合 $B_{i, j, k}$ は $\Gamma$ を分割する（すなわちどの $\Gamma$ 上の点も，ただ一つの $B_{i, j, k}$ に属する）．さらに，$(3i - 1, 3j - 1, 3k - 1)$ は $\Omega$ 上の点であるゆえ，条件 $\Lambda(\Omega)$ よりどの $B_{i, j, k}$ についてもそれに属する $\gamma$ 上の点は高々 $1$ 個である．\
　ここで $1000 = 7 \times 11 \times 13 - 1$ であることに考慮し，以後は $\gamma$ に含まれる点の個数を $XYZ - 1$ であるとし，その上で条件 $\Lambda(\Omega)$ をみたす $\gamma$ の個数を $N$ としよう．すると $\gamma$ と交わりをもたない $B_{i, j, k}$ がただ $1$ つ存在するので，それを $B_{I, J, K}\ (I \in [X], J \in [Y], K \in [Z])$ とおき，$(i, j, k) \neq (I, J, K)$ なる $i, j, k$ に対し $B_{i, j, k} \cap \gamma$ に属する唯一の点を $P_{i, j, k}$ とする．次の補題を与える．

---

**補題 2.**　$\gamma$ が条件 $\Lambda(\Omega_x)$ をみたすための必要十分条件は，$i_1, i_2 \in [X], j \in [Y], k \in [Z], i_1 \neq i_2$ なる組 $(i_1, i_2, j, k)$ をどのように選んでも，$P_{i_1, j, k}$ と $P_{i_2, j, k}$ の $x$ 座標の差が $3$ 以上であることである．

<details><summary>補題 2. の証明<\/summary>
　以下 $2$ つの同値性を示せばよい．

- **P1：**$\gamma$ が条件 $\Lambda(\Omega_x)$ をみたさない．
- **P2：**$i_1, i_2 \in [X], j \in [Y], k \in [Z], i_1 \neq i_2$ なる組 $(i_1, i_2, j, k)$ であって，$P_{i_1, j, k}$ と $P_{i_2, j, k}$ の $x$ 座標の差が $2$ 以下になるものが存在する．

---

**P1 $\Rightarrow$ P2 の証明：**\
　$a, b, c$ を整数とし，$Q (a, 3b - 1, 3c - 1) \in \Omega_x$ と相異なる $P_{i_1, j_1, k_1} (x_1, y_1, z_1), P_{i_2, j_2, k_2} (x_2, y_2, z_2) \in \gamma$ が
$$P_{i_1, j_1, k_1}Q \lt 2，P_{i_2, j_2, k_2}Q \lt 2$$
をともにみたすとする．次の $3$ つを示せばよい．
$$j_1 = j_2，k_1 = k_2，|x_1 - x_2| \leq 2$$
なお，$i_1 \neq i_2$ も示す必要があるが，これは $P_{i_1, j_1, k_1}, P_{i_2, j_2, k_2}$ が相異なることから上記のうち左 $2$ つが示されればただちにしたがう．\
　$l \in \\{1, 2\\}$ を任意に定める．$P_{i_l, j_l, k_l} \in B_{i_l, j_l, k_l}$ であること，および $P_{i_l, j_l, k_l}Q \lt 2$ と補題 1. から
$$3j_l - 2 \leq y_l \leq 3j_l，3b - 2 \leq y_l \leq 3b$$
を得る．よって
$$b - \frac{2}{3} \leq j_l \leq b + \frac{2}{3}$$
が成り立ち，$b, j_l$ が整数であることから $j_l = b$ を得る．これより $j_1 = j_2$ である．同様の議論で $k_1 = k_2$ も得る．また，三角不等式と補題 1. を用いることで
$$|x_1 - x_2| \leq |x_1 - a| + |x_2 - a| \leq 2$$
が導かれる．

**P2 $\Rightarrow$ P1 の証明：**\
　$P_{i_1, j, k} (x_1, y_1, z_1)$ と $P_{i_2, j, k} (x_2, y_2, z_2)$ の $x$ 座標の差が $2$ 以下であるとする．ここで一般性を失うことなく $x_1 \gt x_2$ を仮定する．ここで $\Omega_x$ 上の点 $Q ( \lfloor (x_1 + x_2) \/ 2 \rfloor, 3j - 1, 3k -1 )$ をとる．各 $l \in \\{1, 2\\}$ に対し $P_{i_l, j_l, k_l} \in B_{i_l, j_l, k_l}$ であることから，
$$|y_l - (3j - 1)| \leq 1，|z_l - (3k - 1)| \leq 1$$
がしたがう．さらに
$$x_1 \gt \left \lfloor \frac{x_1 + x_2}{2} \right \rfloor \gt x_2$$
であり，
$$
\begin{aligned}
x_1 - \left \lfloor \frac{x_1 + x_2}{2} \right \rfloor &\lt x_1 - \frac{x_1 + x_2}{2} + 1 \\\\
&= \frac{x_1 - x_2}{2} + 1 \leq 2 \\\\
\left \lfloor \frac{x_1 + x_2}{2} \right \rfloor - x_2 &\leq \frac{x_1 + x_2}{2} - x_2 \\\\
&= \frac{x_1 - x_2}{2} \leq 1
\end{aligned}
$$
なので $| x_l - \lfloor (x_1 + x_2) \/ 2 \rfloor | \leq 1$ も得る．よって，補題 1. から $P_{i_1, j, k} Q, P_{i_2, j, k} Q$ の長さはともに $2$ 未満である．
<\/details>

---

　$I, J, K$ を固定した上で，補題 2. に基づき $\Lambda(\Omega_x)$ をみたす $\gamma$ の個数を求めよう．まず，$(j, k) \neq (J, K)$ なる組 $(j, k)$ それぞれに対し $P_{1, j, k}, P_{2, j, k}, ..., P_{X, j, k}$ の $x$ 座標の定め方は ${}\_{X + 2}\mathrm{C}\_{2}$ 通りずつあることがわかる．ここで $m \geq n \geq 1$ なる整数 $m, n$ に対し以下 $3$ 条件をみたすように赤玉・青玉・白玉を左右一列に並べる方法を $f(m, n)$ とする ( $f(m,n) = {}\_{n+1}\mathrm{C}\_{2} \cdot {}\_{m-n+2}\mathrm{C}\_{2}$ と書き下せるが，ここではこれは用いない)．
- 赤玉・青玉・白玉の個数はそれぞれ $4$ 個，$1$ 個，$m - 1$ 個である．
- 青玉の右側と左側にそれぞれ $2$ 個ずつ赤玉が配置されている．
- 青玉の左側にちょうど $n - 1$ 個の白玉が配置されている．

すると $P_{1, J, K}, ..., P_{I - 1, J, K}$ および $P_{I + 1, J, K}, ..., P_{X, J, K}$ の $x$ 座標の定め方の個数は $f(X, I)$ である．これは $P_{1, J, K}, ..., P_{I - 1, J, K}$ と $P_{I + 1, J, K}, ..., P_{X, J, K}$ をそれぞれ青玉の左側・右側にある白玉と置き換えて考え，これらの $x$ 座標の割り振り方は赤玉の配置に対応するものと考えればよい．よって全体の $x$ 座標の定め方は全部で
$$({}\_{X + 2}\mathrm{C}\_{2})^{YZ - 1} f(X, I)$$
個ある．\
　補題 2. と同様に，$\gamma$ が $\Lambda(\Omega_y), \Lambda(\Omega_z)$ をみたすことと同値な条件として，それぞれ $\gamma$ に属するすべての点の $y, z$ 座標に課せられる条件と言い換えることができる．したがってこれらの条件をみたす $y, z$ 座標の定め方はそれぞれ
$$({}\_{Y + 2}\mathrm{C}\_{2})^{ZX - 1} f(Y, J)，({}\_{Z + 2}\mathrm{C}\_{2})^{XY - 1} f(Z, K)$$
個ずつあることがわかる．$\gamma$ が $\Lambda(\Omega)$ をみたすことはこれが $\Lambda(\Omega_x), \Lambda(\Omega_y), \Lambda(\Omega_z)$ をすべてみたすことと同値であり，$x, y, z$ 座標は互いに独立して定められるので，$\Lambda(\Omega)$ をみたす $\gamma$ は
$$({}\_{X + 2}\mathrm{C}\_{2})^{YZ - 1}({}\_{Y + 2}\mathrm{C}\_{2})^{ZX - 1}({}\_{Z + 2}\mathrm{C}\_{2})^{XY - 1} f(X, I)f(Y, J)f(Z, K)$$
個ある．これを組 $(I, J, K)$ のとり得る範囲すべてに関して総和をとったものが $N$ に等しい．そこで正整数 $m$ に対し
$$F(m) = \sum_{n = 1}^{m} f(m, n)$$
と定義すると，
$$N = ({}\_{X + 2}\mathrm{C}\_{2})^{YZ - 1}({}\_{Y + 2}\mathrm{C}\_{2})^{ZX - 1}({}\_{Z + 2}\mathrm{C}\_{2})^{XY - 1} F(X)F(Y)F(Z)$$
と表せる．ところで $F(m)$ は，先ほどの $f(m, n)$ の定義における青玉の左側にある白玉の個数の制約をなくして赤玉・青玉・白玉を左右一列に並び変える方法の個数に等しいので $F(m) = {}\_{m + 4}\mathrm{C}\_{5}$ であり，よって
$$N = ({}\_{X + 2}\mathrm{C}\_{2})^{YZ - 1}({}\_{Y + 2}\mathrm{C}\_{2})^{ZX - 1}({}\_{Z + 2}\mathrm{C}\_{2})^{XY - 1} {}\_{X + 4}\mathrm{C}\_{5} \cdot {}\_{Y + 4}\mathrm{C}\_{5} \cdot {}\_{Z + 4}\mathrm{C}\_{5}$$
である．特に $(X, Y, Z) = (7, 11, 13)$ の場合は
$$N = 2^{377} \cdot 3^{452} \cdot 5^{76} \cdot 7^{79} \cdot 11^{2} \cdot 13^{92} \cdot 17$$
なので，解答すべき値は $\mathbf{1079}$ である．
公式解説
https://onlinemathcontest.com/contests/omce003/editorial/9224
　三次元空間において，$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$ の値を解答して下さい．

<details><summary>解答形式について<\/summary>
　たとえば，もし求める値が $N = 2^{34} \times 5^{67} \times 89$ となったときは，
$$34 + 67 + 1 = 102$$
なので，この場合の解答すべき値は $102$ となります．
<\/details>