说明

时间限制：1 Sec 内存限制：256 MB 输入文件：triple.in 输出文件：triple.out

给定三个正整数 $a,b,c$。请找出所有满足下面条件的三元正整数组 $(x,y,z)$，并求所有三元组中 $z$ 的总和。

答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

条件：

1. 将 $x,y,z$ 写成二进制时，各自二进制中 $1$ 的个数分别为 $a,b,c$。

2. $x>y>z$。

3. $x \operatorname{or} y \operatorname{or} z = 2^{a+b+c}-1$。

其中 $\operatorname{or}$ 代表按位按位或。

输入格式

第一行三个整数 $a,b,c$。

输出格式

输出所有满足条件的三元组 $(x,y,z)$ 的 $z$ 之和对 $10^9+7$ 取模的值。

样例

样例 1

2 2 1

17

样例说明：

满足条件的 $(x,y,z)$ 用二进制表示共有 $8$ 组：

$(11000, 00110, 00001)$

$(11000, 00101, 00010)$

$(10100, 01010, 00001)$

$(10100, 01001, 00010)$

$(10010, 01100, 00001)$

$(10010, 01001, 00100)$

$(10001, 01100, 00010)$

$(10001, 01010, 00100)$

所有 $z$ 的总和：$1+2+1+2+1+4+2+4=17$。

样例 2

1 1 1

1

样例说明：

满足条件的三元组仅有 $(4,2,1)$ 这一组。

样例 3

100 100 100

208072283

样例说明：

注意输出对 $10^9+7$ 取模。

数据范围

对于 20% 的数据，$a,b,c \le 10$。

对于 40% 的数据，$a,b,c \le 1000$。

对于 100% 的数据，$1 \le a,b,c \le 10^5$。