　$n=500$ とし,  一般に $2n\times 2n$ のマス目に $2n^2-1$ 個の石を条件をみたすように置くことを考える. 各行には高々 $n$ 個しか石を置けないことから, ある $k$ について上から $k$ 行目に $n-1$ 個, 残りの $2n-1$ 行に $n$ 個の石を置くしかない. 対称性より $k\leq n$ の場合を考えて $2$ 倍すればよい.\
　ここで, マス目全体を白黒の市松模様に塗り分けることを考えよう. このとき $k$ 行目以下の石はすべて同じ色のマスに置かれている. 一般性を失わずこれが黒色である場合のみを考えて $2$ 倍する. ここで $k\neq 2$ ならば, $k$ 行目以上の石もすべて黒色のマスに置かれていることがわかるから,  $k$ 行目の配置のみを考えて $n$ 通りである.\
　以下 $k=2$ の場合を考える. 下図において☆印に石を置く場合, $1$ 行目の配置は一意に定まり, $2$ 行目の残りの配置は◯印の選択となるため $n-1$ 通りである. ☆印に石を置かない場合, $2$ 行目の残りの配置は一意に定まり, $1$ 行目は△印のどちらかに石を置くかのみ自由に選択できる. すなわち合計で $n+1$ 通りである.\
　以上より全体では $2\times2\times((n-1)\times n+(n+1))=4n^2+4$ 通りで, ここでは特に $\textbf{1000004}$ である.

![figure 1](\/images\/GzXabrMl13djL92jlwdQGSslzKURXEz754TPIIDi)
公式解説
https://onlinemathcontest.com/contests/omc046/editorial/1370
　$1000\times 1000$ のマス目上に, 以下の条件をみたすように $499999$ 個の石を置く方法は何通りありますか？

- 各マスに置かれた石は高々 $1$ 個である.
- 互いに隣り合う任意の $2$ マスの組について, その両方に石が置かれていることはない.