Sau những ngày học tập mệt mỏi, Copium thường tự thưởng cho mình đi chơi ở Escape Room - nổi tiếng với những màn phòng giải đố vô cùng hấp dẫn ở Việt Nam. Vốn là một người trên thông thiên văn, dưới tường địa lý nên Copium chọn cho mình phòng chơi khó nhất. Sau một hồi quan sát, Copium dùng một miếng giấy để vẽ lại bản đồ của căn phòng dưới dạng bảng gồm ~n~ dòng ~m~ cột, các dòng được đánh số ~x~ đến ~x+n-1~ từ trên xuống dưới và các cột được đánh số ~x~ đến ~x+m-1~ từ trái qua phải, gọi ô ~(i, j)~ là ô nằm trên dòng thứ ~i~ và cột thứ ~j~ của bảng. Copium hiện đứng ở ô ~(x, x)~ của bảng và cần đi chuyển đến ô ~(x+n-1, x+m-1)~. Nhiệm vụ chính để vượt qua căn phòng này là Copium phải xác định quãng đường ngắn nhất mỗi bước mà anh đó sẽ chỉ đi sang ô bên phải hoặc bên dưới. Biết mọi ô ~(i, j)~ đều có giá trị là ~i \times j~ và độ chính xác của một con đường được tính bằng ước chung lớn nhất của các giá trị các ô nằm trên con đường đó. Hãy giúp Copium xác định tổng độ chính xác của mọi con đường có thể để anh có thể vượt qua căn phòng.

Input

• Dòng đầu tiên chứa số nguyên ~t~ là số bản đồ của căn phòng mà Copium định vẽ ~ ( 1 \leq t \leq 1000 )~
• ~t~ dòng sau, mỗi dòng gồm ~3~ số nguyên lần lượt là ~x~, ~n~, ~m~ ~(1 \leq x \leq 10^{18}, 1 \leq n, m \leq 5 \times 10^ 5)~

Output

• In ra ~t~ dòng, ứng với mỗi dòng là tổng độ chính xác của mọi con đường, vì đáp án có thể là số rất lớn nên được chia lấy dư cho ~10^9+7~

Sample Input #1

1
2 2 3

Sample Output #1

4

Sample Input #2

2
1 5 5
4 3 5

Sample Output #2

70
20

Subtask

• ~20\%~ số test có ~x = 1~
• ~30\%~ số test tiếp theo có ~t \leq 5~
• ~50\%~ số test còn lại không có ràng buộc gì thêm.

Note

Ở sample test đầu tiên được giải thích như sau: