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}](/problems/infinite2darray/file/statement/en/img-0001.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 |