Silent, Grumpy and Pilyulkin play a card game for three. The rules of the game are as follows.
First, each of the three players has a deck of cards.
There are N cards in Pilyulkin's deck, M cards in Silent Man's deck, and K cards in Grumbler's deck. Each card has a letter p, m or v written on it. The order of cards in decks cannot be changed. The players take turns. Pilyulkin goes first.
If there is at least one card in the current player's deck, discard the top card in the deck.
Then the next turn goes to the player whose name begins with the letter on the discarded card. For example, if the card says "p", the next turn goes to Pilyulkin.
If the current player's deck is empty, the game ends and the current player wins the game.
There are
3N + M + K possible layouts for three players' starting decks.
How many of these patterns will lead Pilyulkin to victory? Since the answer can be large, print it modulo 1000000007 (= 10
9 +7).
Input
The input is three integers N, M and K (2<=N, M, K <=3*10
5).
Imprint
Print the number of patterns winning for Pilyulkin modulo 1000000007 (= 10
9 +7).
Examples
| # |
Input |
Output |
Explanation |
| 1 |
1 1 1 |
17 |
If Pilyulkin's card is p, then Pilyulkin will win regardless of the Silent and Grumpy cards. There are 3 × 3 = 9.
If Pilyulkin's card is m, Pilyulkin will only win when Silent's card is p, or when Silent's card is v and Grumble's card is p. There are 3 + 1 = 4 such templates in total.
If Pilyulkin's card is v, Pilyulkin will only win when Grumpy's card is p, or when Grumpy's card is m and Grumpy's card is p. There are 3 + 1 = 4 such templates in total.
Thus, there are 9 + 4 + 4 = 17 patterns in total that will lead to Pilyulkin's victory. |
| 2 |
4 2 2 |
1227 |
|
| 3 |
1000 1000 1000 |
261790852 |
|