　点に対して時計回りに $1,2,\ldots,1999$ と番号を振る．求める場合の数は，これらの点を自己交差のない $1$ 本の折れ線で繋ぐ方法の総数であると表現できる．\
　点 $1$ が折れ線の両端のひとつとなっている場合を考える. 点 $1$ から一本目の線分を伸ばすとき, 自己交差をもたないようにするには点 $2$ または点 $1999$ を選ぶしかない. $2$ 本目以降も同様に「右」か「左」を選んでいくので, 最後の $1998$ 本目を除きそれぞれ $2$ 通りずつである. よって, 点 $1$ から折れ線を伸ばす方法は $2^{1997}$ 通りである.\
　それぞれの点から伸ばすことを考えれば, 同じものを $2$ 通りずつ重複して数えているので,
$$M = 2^{1997} \times 1999 \times \frac{1}{2} = 1999 \times 2^{1996}$$
　これを $1999^2$ で割った余りは, $2^{1996}$ を $1999$ で割った余りに $1999$ を掛けたものである. Fermatの小定理より $1999$ を法として $2^{1998} \equiv 1$ だから, $2^{1996} \equiv 4^{-1} \equiv 500$. よって解答すべき値は $1999 \times 500 = \textbf{999500}$.
公式解説
https://onlinemathcontest.com/contests/omc124/editorial/3332
　円周上に $1999$ 個の点があります．\
　これらを次の条件を満たすように $1998$ 本の線分で結ぶ方法は $M$ 通りあります．

- どの線分も相異なる $2$ 点を結ぶ．
- どの $2$ 点についても，それらを結ぶ線分は高々 $1$ 本である．
- どの $2$ 点についても，$1$ 本以上の線分を辿ることで行き来できる．
- どの $2$ 本も端点を除いて共有点をもたない．
- どの点についても，それを端点とする線分は高々 $2$ 本である．

このとき，$M$ を $1999^2$ で割った余りを求めて下さい．ただし，裏返したり回転したりして一致するものも異なるものとして数えます．また，$1999$ は素数です．