题目描述

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)$ で割った余りを出力してください。

输入格式

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

$N$ $M$ $K$

输出格式

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

题目大意

三人$a$, $b$, $c$面前分别有 $N$ ,$M$ , $K$ 张牌, 每张牌上写了$a$,$b$,$c$中的一个, 规则如下：

第一回合是$a$的回合,若轮到某个玩家行动时他面前没牌了,该玩家获胜

否则拿出牌堆中的一张牌，丢掉它，并进入该牌上写着的玩家的回合 游戏开始前牌的所有情况共 $3^{n+m+k}$ 种

求 $a$ 获胜的情况数 对 $1e9+7$ 取模

感谢@YJMSTR 提供的翻译

1 1 1

17

4 2 2

1227

1000 1000 1000

261790852

提示

制約

• $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$ 点が与えられる。

Sample Explanation 1

- 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$ 通りとなります。