Tiling the 2×n Grid with Rectangular Weapons

An alien space station is approximated as a 2×n grid. In your inventory, you have infinitely many rectangular weapons of shape 1×x for any positive integer x. Each such weapon can be rotated by 90° (so a 1×x piece can also be used as an x×1 rectangle). When used, a weapon destroys everything within its rectangular range. However, if any part of the effect spills outside the target area (the grid), it will continue endlessly and cause collateral damage.

To avoid harming innocent civilizations, the commander decides to exactly cover the station using exactly k weapons (you may use the same type multiple times) so that there is no overlap and no cell is left uncovered. In other words, you are given a 2×n grid and infinitely many copies of all 1×x rectangles (with x a positive integer). A placement is valid if and only if the grid is completely tiled by exactly k of these rectangles. Note that when a rectangle is used in its original 1×x orientation it covers one row and x consecutive columns, and if used after a 90° rotation (x×1) it covers x consecutive rows and one column. Since the grid has only 2 rows, a rotated rectangle can only be used if x ≤ 2.

There are two ways to cover a full column by weapons:

• Vertical placement: Use a rotated 1×2 weapon (which becomes 2×1) to cover an entire column. This uses 1 weapon.
• Horizontal placement: Use two 1×x weapons (without rotation) placed in parallel, one in each row, covering the same x consecutive columns. When x = 1 this amounts to covering the column by two independent 1×1 placements. For x ≥ 2, these two pieces together cover a 2×x block. This option uses 2 weapons.

Thus, if you consider tiling from left to right, one may cover the leftmost part of the board by either:

• A vertical placement over 1 column (cost = 1 weapon).
• A horizontal pair covering L consecutive columns (cost = 2 weapons), where L can be any integer from 1 to n. (Note that L = 1 in the horizontal case is equivalent to covering the column with two individual 1×1 pieces.)

Let \(\mathrm{DP}[n][k]\) denote the number of ways to tile a 2×n grid using exactly k weapons. Then for \(n \ge 1\), we have the recurrence:

[ \mathrm{DP}[n][k] = \mathrm{DP}[n-1][k-1] + \sum_{L=1}^{n} \mathrm{DP}[n-L][k-2], \quad \text{with } \mathrm{DP}[0][0] = 1 \text{ and } \mathrm{DP}[0][k] = 0 \text{ for } k > 0. ]

Your task is to compute \(\mathrm{DP}[n][k]\), i.e. the number of tilings of a 2×n grid using exactly k rectangles.

inputFormat

The input consists of a single test case with two integers n and k (1 ≤ n, and k is such that a tiling is possible).

outputFormat

Output a single integer: the number of valid tilings of the 2×n grid using exactly k weapons.

sample

1 1

1