配点 : $200$ 点

問題文

シカのAtCoDeerくんは一列に並んだ $N$ 個のボールをそれぞれ $K$ 色のペンキの色のうちのどれかで塗ろうとしています。見栄えが悪くならないように、隣り合ったボールは別の色で塗ることにします。ボールの塗り方としてあり得るものの個数を求めてください。

制約

• $1 \leq N \leq 1000$
• $2 \leq K \leq 1000$
• 答えは $2^{31}-1$ 以下

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

出力

ボールの塗り方としてあり得るものの個数を出力せよ。

2 2

2

色を$0$,$1$で表すと、左のボールを$0$で塗り、右のボールを$1$で塗る という方法と、 左のボールを$1$で塗り、右のボールを$0$で塗る という方法の$2$通りがあります。

1 10

10

ボールは一つしか無いため,$10$色のうちどれを使っても良いので答えは$10$通りです。

10 8

322828856