OMC186(F)

点数: 700

Writer: HighSpeed

　ある国には $3000$ 個の都市があり，それぞれの都市に，都市 $1, \ldots, 3000$ と番号が振られています．これらの都市の間に，相異なる $2$ 都市間を結ぶ双方向に行き来可能な道を何本か引く方法であって，以下の条件を満たすものが $M$ 通りあるとします．

• 任意の都市から任意の別の都市へ，必要ならばいくつかの都市を経由して，引かれている道だけを使って必ずたどり着くことができ，また同じ都市を $2$ 回以上通らない場合，その道順はちょうど $1$ つ存在する．
• 都市 $1,\ldots,1000$ を端点に持つ道は，それぞれ高々 $1$ 本である．
• 都市 $1001,\ldots,2000$ を端点に持つ道は，それぞれ高々 $2$ 本である．
• 都市 $2001,\ldots,3000$ を端点に持つ道は，それぞれ高々 $3$ 本である．

　$\dfrac{M}{3000!} = \dfrac pq$ をみたす互いに素な正整数 $p, q$ に対して，$p \times q$ を $3000$ で割った余りを答えてください．