Description

考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0. 考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0. 给定两个数N和K, 要求计算包含N位数字的有效K-进制数的总数.（2 <= K <= 10; 2 <= N; 4 <= N+K <= 18.） 例如: 1010230 是有效的7位4进制数 注意：0001235 不是7位数, 而是4位数.

Input Format

两个十进制整数N和K。

Output Format

一个十进制正整数，为包含N位数字的有效K-进制数的总数。

2
10​

90​

Hint

如果一个数为k进制，那么这个数的每一位上的数应不超过k

Source

搜索 DFS