4121. Solutions

Medium递归函数动态规划

时间限制:2000 ms

内存限制:512 MiB

题面

一座建筑物修建了 nn 级台阶,一个机器人可选择一步跨越 1,2,...,k1,2,...,k 级台阶从下向上移动。计算共计有多少种不同的跨越方式正好到达顶端。 例如:n=4,k=2n=4,k=2 ,可能的跨越方式为:1+1+1+1; 1+1+2; 1+2+1; 2+1+1; 2+2, 共 55 种不同的跨越方式。

输入格式

22 个整数 nn (1n64)(1 \leq n \leq 64)kk (1kn)(1 \leq k \leq n),整数之间用一个空格分隔。

输出格式

不同跨越方式的种数。

样例

输入

64 1

输出

1

输入

4 2

输出

5

输入

64 2

输出

17167680177565