You might have seen Internet's greatest meme (later turned into a template) - Loss (The image on the left). This was initiated when a popular comic strip "Ctrl-Alt-Del" suddenly published a dark story, moving away from their regular comic tone. Internet community jumped on the occasion and turned the minimalist version of Loss (the second image) to a popular meme template.
Now, Ross Geller is at a "loss". He needs to go to his job from his flat. His flat is at the (0,0) position of a grid and his office is at the (x,y) co-ordinate. (0,0) denotes the top-leftmost point, whereas (x,y) is the bottom-rightmost point of the grid (You can see the grid configuration for x=4, y=2 in the figure below). He can move around the grid in a hovercraft which can only go in 4 directions after pressing the buttons as shown in the pic. Not a surprise that the buttons represent the four figures of the "Loss " meme, and the directions do so too. The figure below shows where these four buttons take Ross from (x,y).
Find the number of ways Ross can go from (0,0) to (x,y) using only these possible four buttons.
Input
Each line of input will consist of two integers x and y **(1<= x,y<=1000)**separated by a single space. Each line will be separated by a newline. You need to take inputs until you encounter "End of file" (EOF).
Output
Each corresponding line of output will print the number of ways Ross can reach from (0, 0) to (x,y) using the given buttons. Each lines will be separated by a newline. Print the result modulo 109+7.
Sample
| Input | Output |
|---|---|
1 2 2 3 2 2 3 1 1 3 1 1 | 2 6 5 3 2 1 |
The grid picture also explains the result for the first sample input 1 2 . Ross can go to this place in two ways: pressing buttons (i) 1 & 3, (ii) 3 && 1 in order.
