Description

在两层楼之间有N阶楼梯，规定上楼梯每步可跨1到M阶，那么，上得楼梯，可有多少种方法呢？例如，对于4阶的楼梯，每步最大可跨2阶，便有1-1-1-1，1-2-1，1-1-2，2-1-1，2-2这5种方法。

Input

多组数据。每组数据含整数n、m（1<=n<=30,1<=m<=2）,分别表示楼梯阶数和一步可跨的最大阶数。

Output

对于每组数据，输出一行共有多少种楼梯走法。

Sample

Input

4 2
10 2

Output

5
89