D. Зөв олонлог

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

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

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

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

Та бүхний мэдэж байгаачлан $n$ зангилаатай ба $n - 1$ ирмэгтэй чиглэлгүй холбоост графыг мод гэж нэрлэдэг. Танд $d$ бүхэл тоо ба $n$ зангилаанаас бүрдсэн мод өгөгдөнө. $i$ зангилаа бүрийн утга нь $a_{i}$ байна.

Хэрвээ дараах нөхцөлийг хангасан бол модны зангилаануудын $S$ олонлогийг бид зөв гэж нэрлэнэ:

  1. $S$ нь хоосон биш.
  2. $S$ нь холбоост байна. Өөрөөр хэлбэл, хэрэв $u$ ба $v$ нь $S$-н зангилаанууд бол $u$ ба $v$-н хоорондоо энгийн зам дээр бүх зангилаанууд байрлах ёстой мөн $S$-д харъяалагдах ёстой.
  3. .

Таны даалгавар бол зөв олонлогийг тоолох юм. Үр дүн нь маш их байж болох учир, та $1000000007$ ($10^{9} + 7$)-д хуваасан үлдэгдлийг хэвлэх ёстой.

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан хоёр бүхэл $d$ ($0 ≤ d ≤ 2000$) ба $n$ ($1 ≤ n ≤ 2000$) тоонуудыг агуулна.

Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг эерэг бүхэл $a_{1}, a_{2}, ..., a_{n}$($1 ≤ a_{i} ≤ 2000$) тоонууд байна.

Дараагийн $n - 1$ мөр бүр хос бүхэл $u$ ба $v$ ($1 ≤ u, v ≤ n$) тоонуудыг агуулна. Эдгээр нь $u$ болон $v$-гийн хоорондох ирмэгийг илэрхийлнэ. Мэдээж эдгээр ирмэгүүд нь модыг бүрдүүлнэ.

Гаралт

Зөв олонлогийн тоог $1000000007$-д хуваагаад үлдэгдлийг хэвлэ.

Орчуулсан: Даариймаа

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

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

Тэмдэглэл

Эхний жишээнд, яг 8-н зөв олонлог байна: ${1}; {2}; {3}; {4}; {1, 2}; {1, 3}; {3, 4}$ ба ${1, 3, 4}$. Олонлог ${1, 2, 3, 4}$ нь зөв биш, учир нь гурав дахь нөхцлийг хангахгүй байна. Олонлог ${1, 4}$ нь гурав дахь нөхцлийг хангана, гэвч хоёр дахь нөхцөл биелэхгүй байна.

Сэтгэгдлүүдийг ачааллаж байна...