该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

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

Format

Input

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

Output

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

Sample 1

Input

4 2
10 2

Output

5
89

Limitation

1s, 1024KiB for each test case.

Source

OPS Original