Hide

# Problem IInfinite 2D Array

We define an infinite two dimensional array $F$ using the following formula:

• $F_{0, 0} = 0$,

• $F_{0, 1} = F_{1, 0} = 1$,

• For $i \ge 2$, $F_{i, 0} = F_{i-1, 0} + F_{i-2, 0}$,

• For $i \ge 2$, $F_{0, i} = F_{0, i-1} + F_{0, i-2}$,

• For $i, j \ge 1$, $F_{i, j} = F_{i-1, j} + F_{i, j-1}$.

Here are the first few values of $F$:

Given $x$ and $y$, your task is to calculate $F_{x, y}$.

## Input

The input consists of only a single line, containing $2$ integers $x$ and $y$ $(0 < x, y < 10^6)$.

## Output

Print a single integer — the value of $F_{x, y}$, modulo $10^9 + 7$.

Sample Input 1 Sample Output 1
2 2

6

Sample Input 2 Sample Output 2
1 5

13

CPU Time limit 1 second
Memory limit 1024 MB