D. Төрсөн өдөр

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

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

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

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

Маргааш Хэмидийн дүү Алигийн төрсөн өдөр. Хэмид дүүдээ бэлэг олохыг хүссэн учраас түүнд програмчлалын хүнд бодлого өгөөд хэрвээ зөв бодож чадвал цоо шинэ зөөврийн компьютер авна гэж хэлжээ. Али Хэмид шиг сайн програмист болж чадаагүй байгаа ба тэр ихэнхдээ хуурдаггүй боловч энэ удаа онцгой тохиолдол болж байна. Энэ бол шинэ зөөврийн компьютерын тухай юм. Тиймээс тэр нууцаар танаас тусламж хүсэхээр шийджээ. Энэ бодлогыг бодоход Алид туслана уу.

$n$-оройтой жинтэй мод өгөгдсөн байна. $1$ дугаар орой бол модны үндэс юм. Бид $u$ ба $v$ оройнуудын хоорондох хамгийн богино зам дээрх ирмэгүүдийн жингийн нийлбэрийг $d(u, v)$ гэж тодорхойлсон. Тухайлбал $d(u, u) = 0$. Мөн $v$ орой бүрийн хувьд $d(1, u) = d(1, v) + d(v, u)$ байх бүх $u$ оройнуудын олонлогийг $S(v)$ гэж тодорхойлцгооё. $f(u, v)$ функц нь дараах томъёогоор тодорхойлогдоно:

Өгөгдсөн $q$ ширхэг хос орой бүрийн $f(u, v)$-г тодорхойлох зорилготой юм. Хариулт нь хэтэрхий том байж болох учир хариуг $10^{9} + 7$-д хуваагаад гарсан үлдэгдлийг хэвлэхэд болно.

Оролт

Оролтын эхний мөр нь өгөгдсөн модны оройнуудын тоо болох $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоог агуулна.

Дараагийн $n - 1$ мөр бүр нь зайгаар тусгаарлагдсан $a_{i}, b_{i}, c_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $1 ≤ c_{i} ≤ 10^{9}$) гурван бүхэл тоог агуулах бөгөөд эдгээр нь $a_{i}$ ба $b_{i}$ оройнуудын хоорондох ирмэг $c_{i}$ жинтэй гэдгийг илэрхийлнэ.

Дараагийн мөрөнд өгөгдсөн хос оройнуудын тоо болох $q$ ($1 ≤ q ≤ 10^{5}$) бүхэл тоог оруулна.

Дараа нь $q$ мөрүүд байх ба мөр бүр нь зайгаар тусгаарлагдсан $u_{i}, v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$) бүхэл тоонуудыг агуулах ба энэ нь та $f(u_{i}, v_{i})$-г бодно гэсэн үг.

Эдгээр нь өгөгдсөн модны оройнууд байна.

Гаралт

$q$ ширхэг мөр хэвлэнэ. $i$-р мөрөнд $f(u_{i}, v_{i})$-н утгыг $10^{9} + 7$-д хуваагаад гарсан үлдэгдлийг хэвлэнэ.

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

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

Оролт
5
1 2 1
4 3 1
3 5 1
1 3 1
5
1 1
1 5
2 4
2 1
3 5
Гаралт
10
1000000005
1000000002
23
1000000002
Оролт
8
1 2 100
1 3 20
2 4 2
2 5 1
3 6 1
3 7 2
6 8 5
6
1 8
2 3
5 8
2 6
4 7
6 1
Гаралт
999968753
49796
999961271
999991235
999958569
45130
Сэтгэгдлүүдийг ачааллаж байна...