M. Big Sum

Codeforces

IDCF10286M

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

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 <= i_2$ and $j_1 <= 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 <= q <= 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 <= i_1 <= i_2 <= 10^9$, $0 <= j_1 <= j_2 <= 10^9$). For each query, output the value of the sum modulo $10^9 + 7$. ## Input The first line of the input contains a single integer $q$, the number of queries ($1 <= q <= 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 <= i_1 <= i_2 <= 10^9$, $0 <= j_1 <= j_2 <= 10^9$). ## Output For each query, output the value of the sum modulo $10^9 + 7$. [samples]

**Definitions** Let $ A_{i,j} = 2^i \cdot 3^j $ for all $ i, j \in \mathbb{Z}_{\geq 0} $. **Constraints** 1. $ 1 \leq q \leq 10^4 $ 2. For each query: $ 0 \leq i_1 \leq i_2 \leq 10^9 $, $ 0 \leq j_1 \leq j_2 \leq 10^9 $ **Objective** For each query $ (i_1, i_2, j_1, j_2) $, compute: $$ \sum_{i=i_1}^{i_2} \sum_{j=j_1}^{j_2} 2^i \cdot 3^j \mod (10^9 + 7) $$

API Response (JSON)

{
  "problem": {
    "name": "M. Big Sum",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10286M"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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$.\n\n$$ \\begin...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ A_{i,j} = 2^i \\cdot 3^j $ for all $ i, j \\in \\mathbb{Z}_{\\geq 0} $.\n\n**Constraints**  \n1. $ 1 \\leq q \\leq 10^4 $  \n2. For each query: $ 0 \\leq i_1 \\leq i_2 \\leq 10^9 $, $ 0 \\le...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments