Secret of Chocolate Poles

Count sequences of dark and white chocolate disks, each 1 cm thick except dark thick disks at k cm, alternating colors, starting and ending dark, with total thickness at most l.

Medium4Dynamic programmingCombinatoricsNo attempts yetTime limit1sMemory limit512 MB

Problem

Wendy runs a chocolate shop and wants to display poles of chocolate disks in her showcase. She has three kinds of disks: white thin disks, dark thin disks, and dark thick disks. A thin disk is 11 cm thick and a thick disk is kk cm thick. The disks are piled inside glass cylinders.

Every pole must satisfy all of the following conditions.

  • A pole contains at least one disk.
  • The total thickness of the disks in a pole is at most ll cm.
  • The top disk and the bottom disk of a pole are dark.
  • A disk placed directly on a white disk is dark, and a disk placed directly on a dark disk is white.

Figure A.1 shows six side views of poles. When l=5l = 5 and k=3k = 3, these six are the only side views Wendy can make.

Figure A.1. Six chocolate poles for l=5l = 5 and k=3k = 3

Given ll and kk, count the distinct side views Wendy can make.

Input

The input is a single test case in the following format.

l k

ll is the largest total thickness a pole may have, in centimeters, and kk is the thickness of a thick disk, in centimeters. ll and kk are integers with 1l1001 \le l \le 100 and 2k102 \le k \le 10.

Output

Print the number of distinct patterns.