Three friends, Anna, Bob and Charlie, play ping-pong. Ping-pong is a two-player game, so while two of them play the third simply watches. After a game is over, the player who won stays at the table, and then plays with the person who was watching. For example, if Anna beats Bob, then she plays the next match with Charlie.
One day, their informatics teacher asked them the following question. How many ways could the three have played so that Anna wins exactly a matches, Bob exactly b matches and Charlie exactly c matches? Because this can be a very large number, the teacher is satisfied with the answer modulo 109+7.
We now explain when we consider two ways of playing different. For a way of playing P, let Win(P) be the list of players who win each game and Watch(P) be the list of players who watch each game. Then, two ways of playing P and Q are considered to be different if there is a match i for 1β€iβ€a+b+c where Win(P)iβξ =Win(Q)iβ or Watch(P)iβξ =Watch(Q)iβ.
This question seems pretty difficult for them. Can you help them?
Implementation details
You should implement the following function.
int solve(int a, int b, int c);
This function should return the answer for the given values of a,b and c. It will only be called once per execution by the committeeβs grader.
You may use the following function while implementing your solution.
int combinations (int n, int k);
This will return in constant time (KNβ) mod 109+7, i.e. the binomial coefficient corresponding to n,k, or the number ways of choosing k objects from among n objects, all modulo 109+7. Note that the parameters n and k need to satisfy 0β€kβ€nβ€5Β 000Β 000.
Remember to include the header ping-pong.h!
Sample grader behaviour
The sample grader will read three integers, a,b and c from standard input. It will then call solve(a,b,c), and output the returned value to standard output. The input/output files below work for this grader.
Restrictions
- 0β€a,b,cβ€1Β 000Β 000
| # |
Points |
Restrictions |
| 1 |
9 |
a+b+cβ€12 |
| 2 |
4 |
a+bβ€20,c=0 |
| 3 |
7 |
aβ€1Β 000,bβ€1Β 000,c=0 |
| 4 |
11 |
c=0 |
| 5 |
21 |
1β€a,b,cβ€100 |
| 6 |
22 |
1β€a,b,cβ€1Β 000 |
| 7 |
26 |
No further restrictions. |
Example 1
In order to compactly represent all the different scenarios that could happen, we will use the following notation. If in a game player x beats player y, we denote this by xβy. Anna is player a, Bob is player b and Charlie is player c. We will then show a string of games as a list of such statements: for example, if Anna beats Bob, Charlie beats Anna and then Bob beats Charlie, we represent this by aβb,cβa,bβc.
input
1 1 1
output
6
Explanation
There are only 6 possible scenarios:
- a β b,c β a,b β c
- b β a,c β b,a β c
- a β c,b β a,c β b
- c β a,b β c,a β b
- b β c,a β b,c β a
- c β b,a β c,b β a
Example 2
input
2 2 2
output
24
Explanation
- a β b,a β c,b β a,c β b,c β a,b β c
- a β b,c β a,b β c,a β b,c β a,b β c
- a β b,c β a,b β c,b β a,c β b,a β c
- a β b,c β a,c β b,a β c,b β a,b β c
- b β a,b β c,a β b,c β a,c β b,a β c
- b β a,c β b,a β c,a β b,c β a,b β c
- b β a,c β b,a β c,b β a,c β b,a β c
- b β a,c β b,c β a,b β c,a β b,a β c
- a β c,a β b,c β a,b β c,b β a,c β b
- a β c,b β a,b β c,a β b,c β a,c β b
- a β c,b β a,c β b,a β c,b β a,c β b
- a β c,b β a,c β b,c β a,b β c,a β b
- c β a,b β c,a β b,a β c,b β a,c β b
- c β a,b β c,a β b,c β a,b β c,a β b
- c β a,b β c,b β a,c β b,a β c,a β b
- c β a,c β b,a β c,b β a,b β c,a β b
- b β c,a β b,a β c,b β a,c β b,c β a
- b β c,a β b,c β a,b β c,a β b,c β a
- b β c,a β b,c β a,c β b,a β c,b β a
- b β c,b β a,c β b,a β c,a β b,c β a
- c β b,a β c,a β b,c β a,b β c,b β a
- c β b,a β c,b β a,b β c,a β b,c β a
- c β b,a β c,b β a,c β b,a β c,b β a
- c β b,c β a,b β c,a β b,a β c,b β a
Example 3
input
286 191 90
output
789937023