There are $N$ water lilies growing in a line, 1 meter apart from each other, numbered from 1 to $N$. A frog is sitting on lily number 1. In one move, the frog can jump forward or backward to any lily at a distance of no more than $K$ meters. When the frog jumps off a lily, that lily closes and sinks, and it can no longer be jumped on. How many ways are there for the frog to move to lily number $N$?

Input

A single line containing two space-separated integers $N$ and $K$, where $N$ is the number of lilies, $2 \le N \le 18$, and $K$ is the maximum jump distance, $1 \le K < N$.

Output

A single positive integer — the number of ways the frog can move from lily 1 to lily $N$ according to the rules.

Examples

Input 1

3 2

Output 1

2

Input 2

4 2

Output 2

4