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$.

-----Examples-----
Sample Input:
2 2
Sample Output:
6

Difficulty: competition

Starter code:

Solutions: