問題一覧 > 通常問題

No.1165 Paint Squares

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 29
作問者 : 蜜蜂 / テスター : Mitarushi
お気に入りにしたユーザー ProblemId : 4963 / 自分の提出
問題文最終更新日: 2020-11-22 23:18:01
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

You are given a $P \times Q$ grid of squares.
Each square of this grid is painted with one of color $1,$ color $2,$ color $3,$ color $4$.
Among the colorings obtained in this way, one that satisfies the following condition is called a "good coloring".

Condition: every $2×2$ block of squares in the grid is painted with all different colors.

Among the $4^{PQ}$ ways to paint the grid, how many are good colorings?
Since the answer can be very large, output the remainder when it is divided by $10^9+7$.

Input

$P\ \ Q$

All inputs are integers.
$2 \leq P,Q \leq 10^8$

Output

Output the answer on $1$ line.
Print a newline at the end.

Sample

Sample 1
Input
2 2
Output
24

Since the $4$ squares must all have different colors, there are $4!=24$ good colorings.

Sample 2
Input
31415926 53589793
Output
368445756

Output the remainder when the answer is divided by $10^9+7$.

Source

Nada High School 75th Class Junior High Graduation Commemorative Contest: Paint Squares
writer: Mitsubachi
tester: Mitarushi
Ported in accordance with HackerRank's terms. Some parts have been modified.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。