E. Генерация списков
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для заданных целых чисел $$$n$$$ и $$$m$$$ назовем пару массивов $$$a$$$ и $$$b$$$ целых чисел хорошей, если они удовлетворяют следующим условиям:

  • $$$a$$$ и $$$b$$$ имеют одинаковую длину, пусть их длина равна $$$k$$$.
  • $$$k \ge 2$$$ и $$$a_1 = 0, a_k = n, b_1 = 0, b_k = m$$$.
  • Для каждого $$$1 < i \le k$$$ имеет место следующее: $$$a_i \geq a_{i - 1}$$$, $$$b_i \geq b_{i - 1}$$$, и $$$a_i + b_i \neq a_{i - 1} + b_{i - 1}$$$.

Найдите сумму $$$|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$$$.

Пример
Входные данные
4
1 1
1 2
2 2
100 100
Выходные данные
8
26
101
886336572
Примечание

В первом наборе входных данных, хорошими парами массивов являются

  • $$$([0, 1], [0, 1])$$$, длина = $$$2$$$.
  • $$$([0, 1, 1], [0, 0, 1])$$$, длина = $$$3$$$.
  • $$$([0, 0, 1], [0, 1, 1])$$$, длина = $$$3$$$.

Следовательно, сумма длин будет $$${2 + 3 + 3} = 8$$$.