[ICPC 2020 Nanjing R] Harmonious Rectangle

Luogu

IDLGP9629

Time1000ms

Memory256MB

DifficultyP5

2020O2优化ICPC南京

A vertex-colored rectangle is a rectangle whose four vertices are all painted with colors. For a vertex-colored rectangle, it's harmonious if and only if we can find two adjacent vertices with the same color, while the other two vertices also have the same color with each other. For example, $\begin{bmatrix} 1 & 0\\ 1 & 0 \end{bmatrix}$, $\begin{bmatrix} 0 & 0\\ 1 & 1 \end{bmatrix}$ and $\begin{bmatrix} 1 & 1\\ 1 & 1 \end{bmatrix}$ are harmonious, while $\begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}$ is not (same number for same color, and different numbers for different colors). For each point in $\{(x,y) | 1 \le x \le n, 1 \le y \le m, x,y \in \mathbb{Z}\}$, where $\mathbb{Z}$ is the set of all integers, Kotori wants to paint it into one of the three colors: red, blue, yellow. She wonders the number of different ways to color them so that there exists at least one harmonious rectangle formed by the points, whose edges are all parallel to the $x$- or $y$-axis. That is to say, there exists $1 \le x_1 < x_2 \le n$ and $1 \le y_1 < y_2 \le m$ such that $$\begin{cases} \text{color}(x_1, y_1) = \text{color}(x_1, y_2)\\ \text{color}(x_2, y_1) = \text{color}(x_2, y_2)\\ \end{cases} $$ or $$\begin{cases} \text{color}(x_1, y_1) = \text{color}(x_2, y_1)\\ \text{color}(x_1, y_2) = \text{color}(x_2, y_2)\\ \end{cases} $$ where $\text{color}(x, y)$ is the color of point $(x, y)$. Two coloring plans are considered different if there exists a point having different colors in the two coloring plans. ## Input There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$) indicating the number of test cases. For each test case: The first and only line contains three integers $n$, $m$($1 \le n, m \le 2 \times 10^3$). ## Output For each test case output one line containing one integer indicating the number of different ways of coloring modulo $(10^9 + 7)$. [samples]

Samples

Input #1

Output #1

0
15
16485

API Response (JSON)

{
  "problem": {
    "name": "[ICPC 2020 Nanjing R] Harmonious Rectangle",
    "description": {
      "content": "A vertex-colored rectangle is a rectangle whose four vertices are all painted with colors. For a vertex-colored rectangle, it's harmonious if and only if we can find two adjacent vertices with the sam",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9629"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A vertex-colored rectangle is a rectangle whose four vertices are all painted with colors. For a vertex-colored rectangle, it's harmonious if and only if we can find two adjacent vertices with the sam...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments