题目描述

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

输入格式

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

$N$ $K$

输出格式

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

题目大意

你有N个球，K种颜料

你要把N个球涂上颜料，但是为了美观相邻的两个球不能是一样颜色的。

问有多少种涂色方法？

样例1：输入 2 2 输出 2 样例解释：只有01和10这两种涂色方法

样例2:输入 1 10 输出 10 样例解释：有0,1,2,3,4,5,6,7,8和9这些方法

感谢@RioBlu 提供的翻译

2 2

2

1 10

10

10 8

322828856

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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