M. Большая сумма
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Алсу есть бесконечная таблица $$$A$$$. Строки и столбцы в ней нумеруется целыми числами $$$0$$$, $$$1$$$, $$$2$$$, и т.д. Число в $$$i$$$-й строке и $$$j$$$-м столбце равно $$$A_{i,j} = 2^i 3^j$$$.

$$$$$$ \begin{array}{c||c|c|c|c|c} & 0 & 1 & 2 & 3 & \ldots \\ \hline\hline 0 & 1 & 3 & 9 & 27 & \ldots \\ \hline 1 & 2 & 6 & 18 & 54 & \ldots \\ \hline 2 & 4 & 12 & 36 & 108 & \ldots \\ \hline 3 & 8 & 24 & 72 & 216 & \ldots \\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array} $$$$$$

Помогите Алсу обработать $$$q$$$ запросов вида $$$(i_1,i_2,j_1,j_2)$$$, где $$$i_1 \leq i_2$$$ и $$$j_1 \leq j_2$$$. Для каждого запроса вам нужно вычислить значение

$$$$$$\sum_{i=i_1}^{i_2} \sum_{j=j_1}^{j_2} A_{i,j}$$$$$$ по модулю $$$10^9+7$$$.

Входные данные

Первая строка содержит единственное целое число $$$q$$$, количество запросов ($$$1 \leq q \leq 10^4$$$). Далее идут описания самих запросов. $$$i$$$-я из следующих $$$q$$$ строк содержит четыре целых числа $$$i_1$$$, $$$i_2$$$, $$$j_1$$$, $$$j_2$$$, описание $$$i$$$-го запроса ($$$0 \leq i_1 \leq i_2 \leq 10^9$$$, $$$0 \leq j_1 \leq j_2 \leq 10^9$$$).

Выходные данные

Для каждого из запросов в отдельной строке выведите соответствующую сумму по модулю $$$10^9+7$$$.

Пример
Входные данные
1
1 2 0 1
Выходные данные
24