抽取卡牌

题目描述

小$A$，小$B$，小$C$三个人正在玩一个卡牌游戏，三个人面前的牌堆的牌数分别为$N$，$M$，$K$，每个牌堆的牌都是背面朝上整齐地从下叠到上。

每张牌上写着“小$A$”，“小$B$”，“小$C$”三个人名字中的一个。

游戏规则如下，每一轮有一个人行动，第一轮小$A$先行动：

1. 当某个人行动时，如果它的面前的牌堆没牌了，游戏结束，这个人获胜。
2. 目前行动的人翻开自己面前的牌堆中最上面的牌，取走这个牌，这个牌在后面不再出现。
3. 下一个行动的人的名字即为这个牌上写的名字。

显然，如果牌堆里的牌是不确定的，那么开始游戏前，所有牌的情况一共有$3^{N+M+K}$种。

那么地主小$A$想要知道，在这$3^{N+M+K}$种情况中，能使他获胜的情况有多少种，对$10^{9}+7$取模。

输入格式

输入仅一行，包含三个正整数，分别表示$N$，$M$，$K$。

输出格式

输出仅一行，包含一个非负整数，答案对$10^{9}+7$取模的结果。

数据范围与提示

• 对于$10\%$的数据，$N+M+K \leq 15$；
• 对于$40\%$的数据，$N$,$M$,$K \leq 10^{3}$；
• 对于$80\%$的数据，$N$,$M$,$K \leq 3 \times 10^{5}$；
• 对于$100\%$的数据，$N$,$M$,$K \leq 3 \times 10^{6}$。

样例

1 1 1

17

4 2 2

1227