E. Мод ба хүснэгт

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бяцхан Петя модонд маш их дуртай. Саяхан түүний ээж $2n$ тооны зангилаатай мод түүнд бэлэглэжээ. Петя нэн даруй $2$ мөр, $n$ баганатай тэгш өнцөгт хүснэгтэнд дараах нөхцөлийг хангахуйцаар модоо байрлуулахаар шийджээ. Үүнд:

  1. Хүснэгтийн нүд бүр нь яг нэг модны зангилаанд харгалзах ба эсрэгээрээ модны зангилаа бүр нь яг нэг хүснэгтийн нүдэнд харгалзана.
  2. Хэрэв модны $2$ зангилаа нь ирмэгээрээ холбоотой бол харгалзах нүднүүд нь зэрэгцээ нүднүүд болно.

Одоо Петя хүснэгтэнд модоо байрлуулах хэдэн боломж байгааг бодож байна. Аливаа $2$ байрлуулалтыг модны аль нэг зангилаа нь хүснэгтийн өөр өөр нүдэнд байрласан бол ялгаатай гэж үзнэ. Том тоо Петяг сандаргаж магадгүй учраас хариултыг $1000000007$ $(10^{9} + 7)$-д хуваан үлдэгдлийг хэвлээрэй.

Оролт

Эхний мөр нь $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоог агуулна. Дараагийн $(2n - 1)$ мөрөнд мөр бүрд хоорондоо ирмэгээр холбогдсон оройнуудыг илэрхийлэх $a_{i}$ ба $b_{i}$ $(1 ≤ a_{i}, b_{i} ≤ 2n; a_{i} ≠ b_{i})$ гэсэн $2$ бүхэл тоог агуулна.

Модны оройнуудыг $1$-ээс $2n$ хүртэлх бүхэл тоогоор дугаарлагдсан гэж үзээрэй. Оролтын өгөгдөл дэхь граф мод гэдэг нь буюу, өөрөөр хэлбэл холбоотой, цагирган бус, чиглэлт бус граф гэдэг нь баталгаатай болно.

Гаралт

Хүснэгтэнд модыг байрлуулах шаардлагатай боломжийн тоог $1000000007$-д $(10^{9} + 7)$ хуваасан үлдэгдлийг хэвлэ.

Орчуулсан: Солонго

Жишээ тэстүүд

Оролт
3
1 3
2 3
4 3
5 1
6 2
Гаралт
12
Оролт
4
1 2
2 3
3 4
4 5
5 6
6 7
7 8
Гаралт
28
Оролт
2
1 2
3 2
4 2
Гаралт
0

Тэмдэглэл

Эхний жишээний хувьд хүснэгтэнд модыг байрлуулах бүх $12$ боломжийг дор дүрслэв:

1-3-2    2-3-1    5 4 6    6 4 5  
| | |    | | |    | | |    | | |  
5 4 6    6 4 5    1-3-2    2-3-1  

4-3-2    2-3-4    5-1 6    6 1-5  
  | |    | |        | |    | |  
5-1 6    6 1-5    4-3-2    2-3-4  

1-3-4    4-3-1    5 2-6    6-2 5  
| |        | |    | |        | |  
5 2-6    6-2 5    1-3-4    4-3-1
Сэтгэгдлүүдийг ачааллаж байна...