题目描述

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

输入

1 1 1

输出

17

样例 2

输入

4 2 2

输出

1227

样例 3

输入

1000 1000 1000

输出

261790852

说明/提示

限制条件

• $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 翻译