　一般に $N=1000$ とおく．条件をみたす道の引き方において都市を頂点（都市 $i$ を頂点 $i$ と同一視する），道を無向辺と見なしたグラフ $G$ を考えると，一つ目の条件より $G$ は木である．$G$ を頂点 $3N$ を根とする根付き木と見て，次の操作を $3N-2$ 回行うことを考える．
- **操作．** $G$ の葉である頂点のうち番号が最小であるものおよびそれに繋がる辺を取り除く．

$n$ 回目の操作で取り除かれる辺が結ぶ頂点のうち，辺と共に取り除かれる頂点の番号を $a_n$，そうでない方の番号を $p_n$ とする．このとき
$$a_n=\min\bigl(\\{1,2,\dots,3N\\}\setminus\\{a_1,a_2,\dots,a_{n-1},p_n,p_{n+1},\dots,p_{3N-2}\\}\bigr)$$

が成り立つため，$p_1,\dots,p_{3N-2}$ を定めれば $a_1,\dots,a_{3N-2}$ が定まる．また操作を逆に考えていくことで，はじめの道の組み合わせも一意に定まる．頂点 $i$ の次数は $(p_n=i$ なる $n$ の個数$)+1$ であることに注意すれば，$M$ は $$N+1,N+2,\dots,2N,2N+1,2N+1,2N+2,2N+2,\dots,3N,3N$$ の $3N$ 個の数から $3N-2$ 個を選び，それらを同じ数は区別せずに一列に並べる場合の数に等しいことがわかる．これは簡単な議論により
$$ M = \frac{9N - 1}{2^{N+1} \times 3 \left(3N - 1\right)} \times \left(3N\right)! $$
と求められる．
<details><summary>「簡単な議論」<\/summary>
$$ S_1 \coloneqq \left\\{N + 1, \ldots, 2N\right\\}\mathclose{},\qquad S_2 \coloneqq \left\\{2N + 1, \ldots, 3N\right\\} $$
とする．$S_1$ の相異なる $2$ 頂点から取り除いた場合の数は
$$ {}\_N\mathrm C\_2 \times \frac{\left(3N - 2\right)!}{\left(1!\right)^{N-2} \left(2!\right)^N} = \frac{N \left(N - 1\right) \left(3N - 2\right)!}{2^{N+1}}, $$
$S_1, S_2$ それぞれの頂点から取り除いた場合の数は
$$ N^2 \times \frac{\left(3N - 2\right)!}{\left(1!\right)^N \left(2!\right)^{N-1}} = \frac{N^2 \left(3N - 2\right)!}{2^{N-1}}, $$
$S_2$ の相異なる $2$ 頂点から取り除いた場合の数は
$$ {}\_N\mathrm C\_2 \times \frac{\left(3N - 2\right)!}{\left(1!\right)^{N+2} \left(2!\right)^{N-2}} = \frac{N \left(N - 1\right) \left(3N - 2\right)!}{2^{N-1}}, $$
$S_2$ の同じ頂点から取り除いた場合の数は
$$ N \times \frac{\left(3N - 2\right)!}{\left(1!\right)^N \left(2!\right)^{N-1}} = \frac{N \left(3N - 2\right)!}{2^{N-1}} $$
であるから，これらを足し合わせると
$$ M = \frac{N \left(9N - 1\right) \left(3N - 2\right)!}{2^{N+1}}. $$ 

　あるいは展開した様子を考えれば次が成り立つことからも求められる．
$$M=\left(\frac{(1\times N+2\times N)^2-(1^2\times N+2^2\times N)}{2}+2!\times N\right)\times\frac{(3N-2)!}{(1!)^N(2!)^N}$$
<\/details>  
　したがって $N=1000$ を代入して $\dfrac pq = \dfrac{8999}{2^{1001} \times 3 \times 2999}$ が得られ，Euler の定理などにより求める余りは $\mathbf{2256}$．
公式解説
https://onlinemathcontest.com/contests/omc186/editorial/4335
　都市を頂点, 道を辺としたグラフを考えると, 一つ目の条件はグラフが木であることに対応します.  
次数が $i=1,2,3$ の頂点の個数を $e\_i$ とすると, 各頂点の次数の決め方は  
$$\binom{1000}{e\_{3}}\binom{2000-e\_{3}}{e\_{2}}$$ 
となります. ($e\_{3},e\_{2},e\_{1}$ の順に割り当てていくことを考えると良いです.  )  
ここで, 以下の事実が次数制限付き $\mathrm{Cayley}$  の定理等の通称で知られています.  

---
各頂点に $1,2,\dots,n$ とラベルの付いた $n$ 頂点の木であって, 頂点 $i$ の次数が $d(i)$ (ただし, 頂点数と辺の個数の関係式 $\sum d(i)=2n-2$ は満たすとする. )であるようなものの個数は, 

$$\frac{(n-2)!}{\prod\_{i=1}^{n}(d(i)-1)!}$$
個である.  
---

特に, 今の状況に当てはめると, $e$ を固定したもとで, 条件を満たす木の個数は

$$\frac{(2998)!}{2\^{e\_3}}$$
となります.  

後は $e$ を走らせれば良いです.  
頂点数に関する条件 $e\_{1}+e\_{2}+e\_{3}=3000$ 及び, 辺の本数に関する条件 $e\_{1}+2e\_{2}+3e\_{3}=2999\times 2$ から, $e\_{2}=2998-2e\_{3}$ が必要なので, 上述した二項係数が意味を持つ(すなわちそのような木が実際に存在する) $e\_{3} $ は, $e\_{3}=998,999,1000$ に限られます. よって  
$$M=2998!\left(\frac{1000\*999}{2\^{999}}+\frac{1000\*1001}{2\^{999}}+\frac{1000\*999}{2\^{1001}}\right)$$ 

と計算できます.
Cayleyの定理を用いた解法
https://onlinemathcontest.com/contests/omc186/editorial/4335/319
　ある国には $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$ で割った余りを答えてください．