Для заданных целых чисел \(n\) и \(m\) назовем пару массивов \(a\) и \(b\) целых чисел хорошей, если они удовлетворяют следующим условиям:
Найдите сумму \(|a|\) по всем хорошим парам массивов \((a,b)\). Поскольку ответ может быть очень большим, выведите его по модулю \(10^9 + 7\).
Входные данные состоят из нескольких наборов входных данных. Первая строка содержит одно целое число \(t (1 \leq t \leq 10^4)\) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит два целых числа \(n\) и \(m\) \((1 \leq n, m \leq 5 \cdot 10^6)\).
Гарантируется, что сумма \(n\) по всем наборам входных данных не превышает \(5 \cdot 10^6\), а сумма \(m\) по всем наборам входных данных не превышает \(5 \cdot 10^6\).
Для каждого набора входных данных выведите одно целое число — сумму \(|a|\) по всем хорошим парам массивов \((a,b)\) по модулю \(10^9 + 7\).
В первом наборе входных данных, хорошими парами массивов являются
Следовательно, сумма длин будет \({2 + 3 + 3} = 8\).
4 1 1 1 2 2 2 100 100
8 26 101 886336572
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач