题目描述

考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0.

考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0.

例:
1010230 是有效的7位数
1000198 无效
0001235 不是7位数, 而是4位数.

给定两个数N和K, 要求计算包含N位数字的有效K-进制数的总数.

假设2 <= K <= 10; 2 <= N; 4 <= N+K <= 18.

输入格式

两个十进制整数N和K

输出格式

十进制表示的结果

样例 1

输入

2
10

输出

90

题目来源：吉首大学软件学院；FPS 共享题包，题包内第 9 题。保留原作者与原赛事署名。