← 返回题目列表

AtCoder · arc061_d

F. 三人纸牌游戏

中文机器翻译题面 查看原题

分数: 1100 点

问题陈述

Alice、Bob 和 Charlie 正在玩 三人纸牌游戏,如下:

  • 首先,三名玩家各有一副由一定数量的牌组成的牌组。爱丽丝的牌组有 N 牌,鲍勃的牌组有 M 牌,查理的牌组有 K 卡。每张卡片都有一个字母 a, b or c 。牌组中的牌的顺序不能重新排列。
  • 玩家轮流进行。爱丽丝先走。
  • 如果当前玩家的牌组至少包含一张牌,则丢弃牌组顶部的牌。然后,名字以被丢弃的牌上的字母开头的玩家进入下一个回合。 (例如,如果卡片上写着 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