文理学院程序设计在线练习


K进制数

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 76   Accepted Submission(s): 29
Problem Description

K进制数的基数为K,每位上的数字只能是0~K-1,我们定义长度为N的合法K进制数为(1)长度为N,(2)没有连续的2个0,(3)不能有前导0。如1010230是长度为7的合法4进制数,1000089是长度为7的非法10进制数,000012345是长度为9的非法6进制数。给你N和K,请确定长度为N的合法K进制数的个数。特别地,我们定义长度为0的合法K进制数的个数为1。

Input

输入数据每行包括2个整数N和K(2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 18),一直处理到文件结束。

Output

对于每行输入都要有一行相应的输出,输出长度为N的合法K进制数的个数。

Sample Input
2 2
2 3
Sample Output
2
6
Source

USU Championship 1997