Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Vietnamese] as well.

Ben Fero is a popular guy who likes inventing and solving interesting problems. Last weekend, he found a challenging problem, but he could not solve it on his own, so he decided to ask you for help. Can you help Ben Fero solve this problem? 

You are given three integers $A$, $B$ and $C$. Let's call a triple of integers $(a, b, c)$ *interesting* if it satisfies the following criteria:
$1 ≤ a ≤ A$, $1 ≤ b ≤ B$ and $1 ≤ c ≤ C$
for any two real numbers $x$ and $y$ such that $x \neq 0$ and $y \neq 0$, $ax^{2} + 2bxy + cy^{2} > x^{2} + y^{2}$ holds

You should find the number of interesting triples. Since this number could be very large, compute it modulo $10^{9}+7$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains three space-separated integers $A$, $B$ and $C$.

------  Output ------
For each test case, print a single line containing one integer ― the number of interesting triples modulo $10^{9}+7$.

------  Constraints  ------
$1 ≤ T ≤ 10$
$1 ≤ A, C ≤ 10^{9}$
$1 ≤ B ≤ 5,000$

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ A, B, C ≤ 100$

Subtask #2 (20 points): $1 ≤ A, B, C ≤ 5,000$

Subtask #3 (50 points): original constraints

----- Sample Input 1 ------ 
2
2 5 3
3 2 4
----- Sample Output 1 ------ 
1
6
----- explanation 1 ------ 
Example case 1: There is only one interesting triple: $(2, 1, 3)$.

Example case 2: The interesting triples are $(2, 1, 3)$, $(2, 1, 4)$, $(3, 1, 2)$, $(3, 1, 3)$, $(3, 1, 4)$ and $(3, 2, 4)$.

Source: codechef | Difficulty: HARD
Tags: Matrices

Mathematics


Solutions:
import numpy as np
import math
t_cases = int(input())
MOD = 1000000000 + 7
bmax = 5000
sq_integers = []
sum_sq_integers = []
for i in range(1, bmax + 1):
	sq_integers.append(i * i)
	sum_sq_integers.append(0)
for i in range(0, bmax):
	if i == 0:
		sum_sq_integers[i] = sq_integers[i]
	else:
		sum_sq_integers[i] = sq_integers[i] + sum_sq_integers[i - 1]

def get_sum_sq(a, b):
	if a > b:
		return 0
	if a == 1:
		return sum_sq_integers[b - 1]
	return sum_sq_integers[b - 1] - sum_sq_integers[a - 2]
dp_rem_sq = []
for i in range(1, bmax + 1):
	tmp_lst = []
	sm = 0
	for j in range(0, bmax // 50):
		for k in range(j * 50 + 1, j * 50 + 51):
			if k > i:
				sm += k * k % i
		tmp_lst.append(sm)
	dp_rem_sq.append(tmp_lst)

def f4(a, b, bm, c):
	if a < b or c < b:
		return 0
	return (bm - b + 1 + MOD) % MOD

def f3(a, b, bm):
	if a <= b or b >= bm:
		return 0
	if a < bm * bm // b:
		sqrt_ab = int(math.sqrt(a * b))
		ans = f3(a, b, sqrt_ab) + max(0, bm - max(b, sqrt_ab)) * max(0, a - b)
		return ans % MOD
	ind = bm // 50 - 1
	ans = 0
	if ind >= 0:
		ans = get_sum_sq(b, ind * 50 + 50) - dp_rem_sq[b - 1][ind]
	ans = ans // b % MOD
	for i in range(bm // 50 * 50 + 1, bm + 1):
		if i >= b:
			ans += i * i // b % MOD
			ans = ans % MOD
	ans = (ans - b * max(bm - b + 1, 0) % MOD + MOD) % MOD
	return ans

def f2(a, b, bm, c):
	if a < b or c < b:
		return 0
	tmp = (f3(a, b, bm) + f3(c, b, bm) + f4(a, b, bm, c)) % MOD
	return tmp

def f_501(a, b, c):
	ans = 0
	for i in range(1, b + 1):
		ans += f2(a, i, b, c) % MOD
	ans = (a * b * c % MOD + MOD - ans % MOD) % MOD
	return ans % MOD

def exc(a, x, b, c):
	if 1 <= x and x <= a and (x <= c):
		return max(min(b * b // x, a) - x, 0) + max(min(b * b // x, c) - x, 0) + 1
	return 0

def triple_b(a, b, c):
	if a * c == 0 or b * b - a * c >= 0:
		return 0
	sm = 0
	for i in range(1, b + 1):
		sm = (sm + exc(a, i, b, c)) % MOD
	sm = (a * c - sm + MOD) % MOD
	return sm % MOD
ans = ''
for i in range(0, t_cases):
	(a, b, c) = list(map(int, input().split()))
	sm = 0
	if b <= 100:
		for i in range(1, b + 1):
			sm = (sm + triple_b(a - 1, i, c - 1)) % MOD
	else:
		sm = f_501(a - 1, b, c - 1) % MOD
	ans = ans + str(sm) + '\n'
print(ans, end='')


import math
MOD = 10 ** 9 + 7
B_MAX = 5000
D = [[0] * (B_MAX + 1) for _ in range(B_MAX + 1)]
for b in range(1, B_MAX + 1):
	b_sq = b ** 2
	for i in range(1, b + 1):
		D[b][i] = (b_sq // i + D[b][i - 1]) % MOD

def greater_product(A, C, b):
	b_sq = b ** 2
	ans = 0
	if A <= b and C <= b:
		ans = 0
	elif A > b and C > b:
		s = math.ceil(b_sq / A)
		less_than = (s - 1) * A % MOD
		less_than = (less_than + D[b][b] - D[b][s - 1]) % MOD
		s = math.ceil(b_sq / C)
		less_than = (less_than + (s - 1) * (C - b)) % MOD
		less_than = (less_than + D[b][b - 1] - D[b][s - 1]) % MOD
		less_than = (less_than - b * (b - s)) % MOD
		ans = (A * C - less_than) % MOD
	else:
		if A <= b:
			(A, C) = (C, A)
		s = math.ceil(b_sq / A)
		if s > C:
			ans = 0
		else:
			less_than = (s - 1) * A % MOD
			less_than = (less_than + D[b][C] - D[b][s - 1]) % MOD
			ans = (A * C - less_than) % MOD
	if ans < 0:
		ans += MOD
	return ans
t = int(input())
for _ in range(t):
	(A, B, C) = map(int, input().split())
	A -= 1
	C -= 1
	ret = 0
	for b in range(1, B + 1):
		ret = (ret + greater_product(A, C, b)) % MOD
	print(ret)