Tổng tích nhị thức

Trong một buổi thực hành về xử lý số học, FullHouse Dev đang nghiên cứu về một hàm đặc biệt và cách tính tổng các tích của nó.

Bài toán

FullHouse Dev được định nghĩa một hàm \(f(x,y)\) như sau:

• \(f(x,y) = 1\) nếu \(y = 0\)
• \(f(x,y) = x \times y\) trong các trường hợp còn lại

Nhiệm vụ của nhóm là xử lý \(q\) truy vấn, mỗi truy vấn gồm bốn số nguyên \(a\), \(b\), \(c\) và \(d\). Với mỗi truy vấn, cần tính giá trị: [\sum_{i=a}^b f(i,c) \times f(i,d)]

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(q\) - số lượng truy vấn
• \(q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(a\), \(b\), \(c\) và \(d\)

OUTPUT FORMAT:

• In ra \(q\) dòng, mỗi dòng là kết quả của một truy vấn theo modulo \(10^9 + 7\)

Ràng buộc:

• \(1 \leq q \leq 10^5\)
• \(0 \leq a \leq b \leq 10^5\)
• \(0 \leq c,d \leq 10^5\)

Ví dụ

INPUT

3
0 0 0 1
4 5 1 2
4 5 5 6

OUTPUT

0
74
510

Giải thích

• Ở truy vấn đầu tiên: \(f(0,0) \times f(0,1) = 1 \times 0 = 0\)
• Ở truy vấn thứ hai: \(f(4,1) \times f(4,2) + f(5,1) \times f(5,2) = 4 \times 6 + 5 \times 10 = 24 + 50 = 74\)
• Ở truy vấn thứ ba: \(f(4,5) \times f(4,6) + f(5,5) \times f(5,6) = 20 \times 24 + 1 \times 30 = 480 + 30 = 510\)