407649: GYM102862 M Big Sum

You are given an infinite table $$$A$$$. The rows and columns are indexed by integers $$$0$$$, $$$1$$$, $$$2$$$, and so on. The number in the $$$i$$$-th row and $$$j$$$-th column is equal to $$$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} $$$$$$

You need to process $$$q$$$ queries of the form $$$(i_1,i_2,j_1,j_2)$$$, where $$$i_1 \leq i_2$$$ and $$$j_1 \leq j_2$$$. For each query, you need to calculate the value $$$$$$\sum_{i=i_1}^{i_2} \sum_{j=j_1}^{j_2} A_{i,j}$$$$$$ modulo $$$10^9+7$$$.

The first line of the input contains a single integer $$$q$$$, the number of queries ($$$1 \leq q \leq 10^4$$$). The $$$i$$$-th of the next $$$q$$$ lines contains four integers $$$i_1$$$, $$$i_2$$$, $$$j_1$$$, $$$j_2$$$, the description of the $$$i$$$-th query ($$$0 \leq i_1 \leq i_2 \leq 10^9$$$, $$$0 \leq j_1 \leq j_2 \leq 10^9$$$).

For each query, output the value of the sum modulo $$$10^9+7$$$.

1
1 2 0 1

24