No.2367 Painting Gascket
タグ : / 解いたユーザー数 32
作問者 :
logx
Kak1_n0_tane
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$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もしくは右上の雲マークをクリックしてアカウントを作成してください。