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

A さん、B さん、C さん三个人正在玩如下的卡牌游戏。 - 最开始，三个人分别持有若干张卡牌，每张卡牌上写有 `a`、`b` 或 `c` 中的一个字母。A さん有 $N$ 张，B さん有 $M$ 张，C さん有 $K$ 张。三个人不能改变自己手中卡牌的顺序。 - 游戏从 A さん的回合开始。 - 如果当前轮到的人手中还有至少一张卡牌，则他需要丢弃自己手中最前面的一张卡牌。随后，轮到与丢弃卡牌上字母相同名字的人进行回合（例如，丢弃的卡牌上是 `a`，则轮到 A さん）。 - 如果当前轮到的人手中已经没有卡牌了，则此人获胜，游戏结束。 三个人初始手中卡牌的排列方式共有 $3^{N+M+K}$ 种。请你计算其中有多少种情况下，A さん会成为获胜者。 由于答案可能很大，请输出答案对 $1\,000\,000\,007\ (=10^9+7)$ 取模后的结果。

输入为一行，包含三个整数 $N$、$M$、$K$。

输出一个整数，表示 A さん获胜的方案数，对 $1\,000\,000\,007$ 取模。

### 限制条件 - $1 \leq N \leq 3 \times 10^5$ - $1 \leq M \leq 3 \times 10^5$ - $1 \leq K \leq 3 \times 10^5$ ### 部分得分 - 若 $1 \leq N \leq 1000$，$1 \leq M \leq 1000$，$1 \leq K \leq 1000$ 的数据集全部答对，可获得 $500$ 分。 ### 样例解释 1 - 如果 A さん手中的第一张卡牌是 `a`，无论其他两人手中卡牌如何，A さん都会获胜。这种情况有 $3 \times 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$ 种情况。 由 ChatGPT 4.1 翻译