题目描述

Alice、Bob 和 Charlie 在玩"三人卡牌游戏"，规则如下:

• 起初，每位玩家手上各有一叠卡牌。Alice 的卡牌堆有 $N$ 张，Bob 的卡牌堆有 $M$ 张，Charlie 的卡牌堆有 $K$ 张。每张牌上都写着字母 a、b 或 c。卡牌堆中的卡牌顺序不能改变。
• 玩家轮流行动，Alice 先开始。
• 如果当前玩家的卡牌堆至少有一张卡牌，则将卡牌堆顶的卡牌丢弃。然后，以被丢弃的卡牌上字母开头的玩家获得下一回合的行动权。（例如，如果丢弃的卡牌上写着 a，则 Alice 获得下一回合的行动权。）
• 如果当前玩家的卡牌堆为空，则游戏结束，当前玩家获胜。

在三位玩家初始卡牌堆的情况下，共有 $3^{N+M+K}$ 种可能的情况。其中有多少种情况会导致 Alice 获胜？

由于答案可能很大，输出结果对 $1\\,000\\,000\\,007$ 取模。

约束条件

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

分数

• 通过满足以下条件的测试用例将获得 $500$ 分：$1 \leq N \leq 1000$，$1 \leq M \leq 1000$，$1 \leq K \leq 1000$。

输入

从标准输入读入输入数据，输入格式如下：

$N$ $M$ $K$

输出

输出结果对 $1\\,000\\,000\\,007$ 取模。

示例输入1

1 1 1

示例输出1

17

• 如果 Alice 的卡牌是 a，则不论 Bob 和 Charlie 的卡牌是什么，Alice 都会获胜。共有 $3×3=9$ 种情况。
• 如果 Alice 的卡牌是 b，只有当 Bob 的卡牌是 a，或者当 Bob 的卡牌是 c 而 Charlie 的卡牌是 a 时，Alice 才会获胜。共有 $3+1=4$ 种情况。
• 如果 Alice 的卡牌是 c，只有当 Charlie 的卡牌是 a，或者当 Charlie 的卡牌是 b 而 Bob 的卡牌是 a 时，Alice 才会获胜。共有 $3+1=4$ 种情况。

因此，共有 $9+4+4=17$ 种情况会导致 Alice 获胜。

示例输入2

4 2 2

示例输出2

1227

示例输入3

1000 1000 1000

示例输出3

261790852