Go To Goal

Time limit1sMemory limit512 MB

Summary

Count the sequences of N two-step and M one-step moves totaling 2N+M that never place three two-step moves in consecutive turns, modulo 1e9+7.

Level: Medium7 of 10
Topics: Combinatorics, Dynamic programming, Math, Greedy
Solved: No attempts yet

Problem

Ani is playing a game with one piece and $2N + M + 1$ squares, numbered from $0$ to $2N + M$ . The piece starts on square $0$ . Ani also has $N$ super cards and $M$ normal cards.

On each turn, Ani can use one of her unused cards. If she uses a normal card, the piece moves one square ahead, from square $x$ to square $x + 1$ . If she uses a super card, the piece moves two squares ahead, from square $x$ to square $x + 2$ . Ani cannot use super cards too often: she cannot use three super cards in three consecutive turns.

After $N + M$ turns, the piece must be on square $2N + M$ , the goal. Ani wants to know the number of paths her piece can take to the goal. Two paths are different if the piece is on different squares after the same number of turns.

For example, if $N = 3$ and $M = 1$ , there are two paths the piece can take to the goal:

Use the normal card on the second turn, and the super cards on the first, third, and fourth turns.
Use the normal card on the third turn, and the super cards on the first, second, and fourth turns.

Ani cannot use the normal card on the first turn, because then she would have to use the super cards on the last three turns in a row.

Input

The input begins with a line containing two integers $N$ $M$ ( $1 \le N, M \le 100\,000$ ), the number of super cards and normal cards.

Output

Output one line with the number of paths the piece can take to the goal. The answer can be large, so output it modulo $1\,000\,000\,007$ .

Examples3

Example 1
Input
```
3 1
```
Expected output
```
2
```
Example 2
Input
```
5 1
```
Expected output
```
0
```
Example 3
Input
```
5 2
```
Expected output
```
3
```