Wooden Bridge

Time limit1sMemory limit1024 MB

Summary

Count the distinct bridges of W blocks whose total span is exactly L, where each block shifts by at most 1 unit from the one below, modulo 1e9+7.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

A carpenter wants to build a wooden bridge across a river that is $W$ wide. The bridge is made of $W$ wooden blocks. Each block is 2 units long and 1 unit tall, and the blocks are joined together to form the bridge. For smooth passage, the horizontal overlap between each pair of vertically adjacent blocks must be 1 or 2 units long.

The carpenter wants the bridge to be as long as safely possible, so the distance from the left end of the bridge to the right end is exactly $L$ . Two bridges count as the same shape if shifting one left or right makes it match the other. Count the number of distinct bridge shapes that satisfy these conditions.

Input

The river width $W$ and the distance $L$ from the left end of the bridge to the right end are given.

Output

Print the number of distinct bridge shapes that satisfy the conditions, modulo $10^9 + 7$ .

Constraints

$1 \le W \le 1{,}000$
$2 \le L \le W + 1$

Examples2

Example 1
Input
```
3 3
```
Expected output
```
6
```
Example 2
Input
```
10 5
```
Expected output
```
6678
```