Ping-Pong

Time limit: 0.5s Memory limit: 512MB Input: Output:

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 aa matches, Bob exactly bb matches and Charlie exactly cc matches? Because this can be a very large number, the teacher is satisfied with the answer modulo 109+710^9 + 7.

We now explain when we consider two ways of playing different. For a way of playing PP, let Win(P)Win(P) be the list of players who win each game and Watch(P)Watch(P) be the list of players who watch each game. Then, two ways of playing PP and QQ are considered to be different if there is a match ii for 1≀i≀a+b+c1 \leq i \leq a + b + c where Win(P)iβ‰ Win(Q)iWin(P)_i β‰  Win(Q)_i or Watch(P)iβ‰ Watch(Q)iWatch(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,ba, b and cc. 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 (NK){N}\choose{K} mod 109+710^9 + 7, i.e. the binomial coefficient corresponding to n,kn, k, or the number ways of choosing kk objects from among nn objects, all modulo 109+710^9 + 7. Note that the parameters nn and kk need to satisfy 0≀k≀n≀5Β 000Β 0000 \leq k \leq n \leq 5 \ 000 \ 000.

Remember to include the header ping-pong.h!

Sample grader behaviour

The sample grader will read three integers, a,ba, b and cc from standard input. It will then call solve(a,b,c)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Β 0000 \leq a, b, c \leq 1 \ 000 \ 000
# Points Restrictions
1 9 a+b+c≀12a + b + c \leq 12
2 4 a+b≀20,c=0a + b \leq 20, c = 0
3 7 a≀1Β 000,b≀1Β 000,c=0a \leq 1 \ 000, b \leq 1 \ 000, c = 0
4 11 c=0c = 0
5 21 1≀a,b,c≀1001 \leq a, b, c \leq 100
6 22 1≀a,b,c≀1Β 0001 \leq a, b, c \leq 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 xx beats player yy, we denote this by x→yx → y. Anna is player a\color{red}{a}, Bob is player b\color{cyan}{b} and Charlie is player c\color{blue}{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→ca → b, c → a, b → c.

input

1 1 1

output

6

Explanation

There are only 66 possible scenarios:

  1. a\color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c\color{blue}{c}
  2. b\color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c\color{blue}{c}
  3. a\color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b\color{cyan}{b}
  4. c\color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b\color{cyan}{b}
  5. b\color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a\color{red}{a}
  6. c\color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a\color{red}{a}

Example 2

input

2 2 2

output

24

Explanation

  1. a\color{red}{a} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c\color{blue}{c}
  2. a\color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c\color{blue}{c}
  3. a\color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c\color{blue}{c}
  4. a\color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c\color{blue}{c}
  5. b\color{cyan}{b} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c\color{blue}{c}
  6. b\color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c\color{blue}{c}
  7. b\color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c\color{blue}{c}
  8. b\color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c\color{blue}{c}
  9. a\color{red}{a} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b\color{cyan}{b}
  10. a\color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b\color{cyan}{b}
  11. a\color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b\color{cyan}{b}
  12. a\color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b\color{cyan}{b}
  13. c\color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b\color{cyan}{b}
  14. c\color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b\color{cyan}{b}
  15. c\color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b\color{cyan}{b}
  16. c\color{blue}{c} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b\color{cyan}{b}
  17. b\color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a\color{red}{a}
  18. b\color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a\color{red}{a}
  19. b\color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a\color{red}{a}
  20. b\color{cyan}{b} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a\color{red}{a}
  21. c\color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a\color{red}{a}
  22. c\color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a\color{red}{a}
  23. c\color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a,c\color{red}{a}, \color{blue}{c} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a\color{red}{a}
  24. c\color{blue}{c} β†’ b,c\color{cyan}{b}, \color{blue}{c} β†’ a,b\color{red}{a}, \color{cyan}{b} β†’ c,a\color{blue}{c}, \color{red}{a} β†’ b,a\color{cyan}{b}, \color{red}{a} β†’ c,b\color{blue}{c}, \color{cyan}{b} β†’ a\color{red}{a}

Example 3

input

286 191 90

output

789937023

Log in or sign up to be able to send submissions!