Người Ai Cập cổ đại đã bắt đầu xây dựng các kim tự tháp một thời gian ngắn sau năm ~2700~ trước công nguyên, thời kì hoàng kim của các kim tự tháp dành cho hoàng tộc kéo dài khoảng ~1000~ năm, đến năm ~1700~ trước công nguyên. Trong đó, lớn nhất cũng như nổi tiếng nhất là kim tự tháp tại thành phố ~Giza~, trong đó bao gồm kim tự tháp ~Giza~ của Pharaoh Khufu.

Lấy cảm hứng từ các kim tự tháp của người Ai Cập cổ, Soen đã tạo ra một cái của riêng mình bằng cách sử dụng những con số. Kim tự tháp của Soen được miêu tả gồm cặp số ~(m, n)~. Bắt đầu từ số ~1~, tăng dần đến ~m~ và sau đó lại giảm dần về ~1~, quá trình này sẽ được lặp lại ~n~ lần. Cuối cùng, Soen thắc mắc tổng các số trên kim tự tháp của mình là bao nhiêu, các bạn hãy giúp Soen nhé.

Input:

• Dòng đầu gồm số nguyên ~Q~ là số lượng truy vấn ~(1 \leq Q \leq 10^5)~
• ~Q~ dòng sau, mỗi dòng gồm ~2~ số nguyên ~n, m~ thể hiện dữ liệu kim tự tháp của truy vấn tương ứng ~(1 \leq n, m \leq 10^9)~

Output:

• Gồm ~Q~ dòng, mỗi dòng gồm một số nguyên là tổng các số trên kim tự tháp ~(m, n)~ đó. Vì kết quả có thể rất lớn các bạn hãy in kết quả là phần dư của phép chia khi chia kết quả cho ~10^9 + 7~

Sample Input

1
4 3

Sample Output

33

Subtask

• ~20\%~ số test có ~Q = 1; 1 \leq n, m \leq 10^3~
• ~20\%~ số test tiếp theo có ~Q \le 10^5; 1 \leq n, m \leq 10^3~
• ~60\%~ số test còn lại có ~Q \le 10^5; 1 \leq n, m \leq 10^9~