2 teams play in total During the course of the game, each team gets points, and thus increases its score by 1. The initial score is 0 for both teams. The game ends when
One of the teams gets 25 points and another team has < 24 points ( strictly less than 24). If the score ties at 24:24, the teams continue to play until the absolute difference between the scores is 2. Given the final score of two teams game in the format A:B, can you print the number of different sequences of getting points by teams that leads to this final score?
Input Format The first line contains A and the second line contains B.
Constraints
$0 \leq A$ , $B \leq 10^9$
Output Format Output the number of different sequences of getting points by the teams that leads to the final score A : B. Final means that the game should be over after this score is reached. If the number is larger than 10^9+7, output number modulo 10^9 + 7. Print 0 if no such game ends with the given score.
Example input #00
3 25
Example output #00
2925
Example input #01
24 17
Example output #01
0
You tagged this as dynamic programming, so I'm assuming this is some kind of programming assignment rather than a simple math assignment, so I am going to be a bit more explicit with the mathematics than I would for a mathematics homework assignment.
Suppose you are at a point where the score is 13 vs 7. How many ways could you have gotten that score? Well the previous score was either 12 vs 7 or 13 vs 6. So $F(13, 7) = F(12, 7) + F(13,6)$. If you are very insightful you'll realize that you didn't over count anything, but there is another way to get this same result.
If the score is A:B, how many rounds were played? A + B rounds were played. And the first player won A of them. So there were ${A + B \choose A}$ ways the rounds could have been won. We know from a fellow named Pascal who used to carry a triangle around that ${x \choose y} = {x - 1 \choose y} + {x - 1 \choose y - 1}$. You can use this relation to also give you a nice recursive solution to your problem.
...but the above is only valid if $A \le 25$ and $B \le 25$, or if $A=B$. There is no way to get a score like 37:29, so you need to figure out for what cases $F(A,B) = 0$. Also, for a score like 48:47, there is only 1 valid previous score, so in these cases you'll have a different recursive formula than in the other cases.
With dynamic program you can get a result that is $O(AB)$ for small A,B and $O(A)$ for large A,B.
If you want to go beyond dynamic programming, notice that $F(A,A) \equiv 2F(A - 1, A - 1) \pmod {10^9 + 7}$ for large enough $A$, so you can use modular exponentiation to really speed up your program.