問題一覧 > 通常問題

No.2367 Painting Gascket

レベル : / AI推定難易度 : 1925 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 32
作問者 : Carpenters-Cat / テスター : logx shobonvip Kak1_n0_tane comavius
お気に入りにしたユーザー ProblemId : 6675 / 自分の提出
問題文最終更新日: 2023-06-30 04:17:26
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
yukicoder contest 395 (順位表) の他の問題:

Problem

Pina received a level $K$ gasket as a birthday present.

Here, a level $K$ gasket is a figure defined as follows.

  • When $K = 0$, it is an upward-pointing equilateral triangle.
  • When $K > 0$, it is a downward-pointing equilateral triangle with a level ($K - 1$) gasket of the same size as that triangle attached to each of its sides so that they share the side.

For example, the level $1,\, 2$ gaskets look as follows, respectively.

Level $1$ Level $2$

Pina is going to paint each equilateral triangle part of the level $K$ gasket she received in one color each, using $N$ colors of paint.

However, for the sake of appearance, she has decided that equilateral triangles sharing a line segment of positive length must be painted in different colors. It is also allowed that some colors are not used.

How many ways are there to paint it? Find the count modulo $10^9 + 7$.

Note that colorings that become identical by rotation or reflection are considered different from each other.

Input

$K\ N$

$0 \leq K \leq 10^5$

$1 \leq N \leq 10^9$

$K, N$ are both integers.

Output

$ans$

Output $ans$, the number of ways to paint modulo $10^9+7$, followed by a newline.

Sample

Sample 1
Input
1 3
Output
24

Let color 1 be orange, color 2 be yellow-green, and color 3 be light blue. When the central equilateral triangle of level $1$ is painted in color 1, the colorings fall into the following 4 types.

  • The leftmost type of coloring (all 3 painted in color 2) has 1 way.
  • The second type from the left (2 painted in color 2 and 1 painted in color 3) gives 3 ways through rotation and reflection.

Similarly, the third and fourth types from the left have 3 and 1 ways, respectively.

Therefore, there are 8 ways to paint with the center in color 1.

The same applies when the central equilateral triangle is painted in color 2 or 3, so the answer is 8×3 = 24 ways.

Sample 2
Input
100 1
Output
0

With only 1 color, a level $100$ gasket cannot be painted so as to satisfy the condition.

Sample 3
Input
1000 10
Output
910387022

Note that you must output the remainder modulo $10^9 + 7$.

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