一定出现的那种颜色

题目描述

用编号 1 至 m 的颜色给长度 n 的一行配色，要求相邻颜色不同，而且颜色 1 至少出现一次。求方案数。空行没有出现任何颜色，因此 n=0 的答案为 0。

输入格式

输入 n、m。

输出格式

输出方案数。

样例 1

输入

2 3

输出

4

说明

合法为 12、13、21、31。

样例 2

输入

0 3

输出

0

说明

空行不包含颜色 1。

数据范围

• 0≤n≤25；1≤m≤5；答案使用 long long。