分数: 1100 点
问题陈述
Alice、Bob 和 Charlie 正在玩 三人纸牌游戏,如下:
- 首先,三名玩家各有一副由一定数量的牌组成的牌组。爱丽丝的牌组有 N 牌,鲍勃的牌组有 M 牌,查理的牌组有 K 卡。每张卡片都有一个字母
a,borc。牌组中的牌的顺序不能重新排列。 - 玩家轮流进行。爱丽丝先走。
- 如果当前玩家的牌组至少包含一张牌,则丢弃牌组顶部的牌。然后,名字以被丢弃的牌上的字母开头的玩家进入下一个回合。 (例如,如果卡片上写着
a,爱丽丝进行下一个回合。) - 如果当前玩家的牌库为空,则游戏结束,当前玩家赢得游戏。
有 3^{N+M+K} 三位玩家初始牌组的可能模式。在这些模式中,有多少种会导致爱丽丝获胜?
由于答案可能很大,因此打印计数模数 1\,000\,000\,007 (=10^9+7).
约束
- 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 (=10^9+7).
样本输入 1
1 1 1
示例输出 1
17
- 如果 Alice 的卡是
a,那么无论 Bob 和 Charlie 的牌如何,Alice 都会获胜。 3×3=9 这样的模式。 - 如果 Alice 的卡是
b,只有当 Bob 的牌是时,Alice 才会获胜a,或者当 Bob 的卡是c查理的卡是a。有 3+1=4 这样的模式。 - 如果 Alice 的卡是
c,只有当查理的牌是时,爱丽丝才会获胜a,或者当查理的卡是b鲍勃的卡是a。有 3+1=4 这样的模式。
因此,总共有 9+4+4=17 将导致爱丽丝胜利的模式。
示例输入 2
4 2 2
示例输出 2
1227
示例输入 3
1000 1000 1000
示例输出 3
261790852