F - Card Game for Three Editorial /

Time Limit: 3 sec / Memory Limit: 256 MB

配点 : 1100 点

問題文

A さん、B さん、C さんの 3 人が以下のようなカードゲームをプレイしています。

  • 最初、3 人はそれぞれ a、b、c いずれかの文字が書かれたカードを、A さんは N 枚、B さんは M 枚、C さんは K 枚持っている。3 人は、持っているカードを並べ替えることはできない。
  • A さんのターンから始まる。
  • 現在自分のターンである人がカードを 1 枚以上持っているならば、そのうち先頭のカードを捨てる。その後、捨てられたカードに書かれているアルファベットと同じ名前の人 (例えば、カードに a と書かれていたならば A さん) のターンとなる。
  • 現在自分のターンである人がカードを 1 枚も持っていないならば、その人がゲームの勝者となり、ゲームは終了する。

3 人が最初に配られるカードに書いてある文字の並びは、全部で 3^{N+M+K} 通りの組み合わせがあります。このうち、A さんが勝者となってゲームが終了するのが何通りあるかを求めてください。

答えは大きくなる可能性があるので、1\,000\,000\,007 (=10^9+7) で割った余りを出力してください。

制約

  • 1 \leq N \leq 3×10^5
  • 1 \leq M \leq 3×10^5
  • 1 \leq K \leq 3×10^5

部分点

  • 1 \leq N \leq 1000、 1 \leq M \leq 1000、 1 \leq K \leq 1000 を満たすデータセットに正解した場合は、 500 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N M K

出力

答えを 1\,000\,000\,007 (=10^9+7) で割った余りを出力せよ。

入力例 1

1 1 1

出力例 1

17
  • A さんが a を持っている場合は、他の 2 人の持っているカードに関わらず A さんが勝ちます。これは 3×3=9 通りあります。
  • A さんが b を持っている場合は、B さんが a を持っているか、 B さんが c を持っていてかつ C さんが a を持っている場合に限り A さんが勝ちます。これは 3+1=4 通りあります。
  • A さんが c を持っている場合は、C さんが a を持っているか、 C さんが b を持っていてかつ B さんが a を持っている場合に限り A さんが勝ちます。これは 3+1=4 通りあります。

合計すると、 9+4+4=17 通りとなります。

入力例 2

4 2 2

出力例 2

1227

入力例 3

1000 1000 1000

出力例 3

261790852

Score : 1100 points

Problem Statement

Alice, Bob and Charlie are playing Card Game for Three, as below:

  • At first, each of the three players has a deck consisting of some number of cards. Alice's deck has N cards, Bob's deck has M cards, and Charlie's deck has K cards. Each card has a letter a, b or c written on it. The orders of the cards in the decks cannot be rearranged.
  • The players take turns. Alice goes first.
  • If the current player's deck contains at least one card, discard the top card in the deck. Then, the player whose name begins with the letter on the discarded card, takes the next turn. (For example, if the card says a, Alice takes the next turn.)
  • If the current player's deck is empty, the game ends and the current player wins the game.

There are 3^{N+M+K} possible patters of the three player's initial decks. Among these patterns, how many will lead to Alice's victory?

Since the answer can be large, print the count modulo 1\,000\,000\,007 (=10^9+7).

Constraints

  • 1 \leq N \leq 3×10^5
  • 1 \leq M \leq 3×10^5
  • 1 \leq K \leq 3×10^5

Partial Scores

  • 500 points will be awarded for passing the test set satisfying the following: 1 \leq N \leq 1000, 1 \leq M \leq 1000, 1 \leq K \leq 1000.

Input

The input is given from Standard Input in the following format:

N M K

Output

Print the answer modulo 1\,000\,000\,007 (=10^9+7).

Sample Input 1

1 1 1

Sample Output 1

17
  • If Alice's card is a, then Alice will win regardless of Bob's and Charlie's card. There are 3×3=9 such patterns.
  • If Alice's card is b, Alice will only win when Bob's card is a, or when Bob's card is c and Charlie's card is a. There are 3+1=4 such patterns.
  • If Alice's card is c, Alice will only win when Charlie's card is a, or when Charlie's card is b and Bob's card is a. There are 3+1=4 such patterns.

Thus, there are total of 9+4+4=17 patterns that will lead to Alice's victory.

Sample Input 2

4 2 2

Sample Output 2

1227

Sample Input 3

1000 1000 1000

Sample Output 3

261790852