Hide

Problem E
Infinite 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$:

\includegraphics[width=0.8\textwidth ]{I.png}

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

Please log in to submit a solution to this problem

Log in