[ARC061F] 3人でカードゲーム

三人$a$, $b$, $c$面前分别有 $N$ ,$ M$ , $K$ 张牌, 每张牌上写了$a$,$b$,$c$中的一个, 规则如下： 第一回合是$a$的回合,若轮到某个玩家行动时他面前没牌了,该玩家获胜 否则拿出牌堆中的一张牌，丢掉它，并进入该牌上写着的玩家的回合 游戏开始前牌的所有情况共 $3^{n+m+k}$ 种 求 $a$ 获胜的情况数 对 $1e9+7$ 取模 感谢@YJMSTR 提供的翻译

[problemUrl]: https://atcoder.jp/contests/arc061/tasks/arc061_d 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) $ で割った余りを出力せよ。

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