E. Жууху ба квадратууд

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

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

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

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

Жуухуд $n$ ба $m$ хоёр бүхэл тоо байна. $0 ≤ x ≤ n$, $0 ≤ y ≤ m$ байх хавтгайн $(x, y)$ цэгийг онцгой цэг гэж нэрлэдэг. $x$, $y$ нь ямар нэг бүхэл тоонууд ба Жууху $(x, y)$, $(x + 1, y)$, $(x + 1, y + 1)$, $(x, y + 1)$ цэгүүд дээр оройтой квадратыг нэгж квадрат гэж тодорхойлжээ.

Өнцгүүд нь онцгой цэгүүд дээр байрласан бүх квадратыг (талууд нь координатын тэнхлэгтэй параллель байх албагүй) авч үзье. Жууху эдгээр квадратуудын дотор байгаа нэгж квадрат бүрийн дотор цэг зурсан. Эдгээр бүх үйлдлийн дараа зарим нэгж квадратуудад хэд хэдэн цэгүүд байж болно. Одоо Жууху хавтгай дээр түүний зурсан хэдэн цэг байгаа бол гэж бодож байна. Энэ тоог $1000000007$ $(10^{9} + 7)$-д хуваагаад гарах үлдэгдлийг ол.

Оролт

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

Дараагийн $t$ мөрөнд мөр бүрд тестийг илэрхийлэх: $n$, $m$ $(1 ≤ n, m ≤ 10^{6})$ хоёр бүхэл тоо байна.

Гаралт

Тест бүрийн хувьд цэгүүдийн нийт тоог $1000000007$ $(10^{9} + 7)$-д хуваагаад гарсан үлдэгдлийг нэг нэг мөрөнд хэвлэнэ.

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

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

Оролт
4
1 3
2 2
2 5
3 4
Гаралт
3
8
26
58
Сэтгэгдлүүдийг ачааллаж байна...