2081 : 舰队管理

时间限制:0 Sec 内存限制:0 MiB
提交:82 答案正确:24

提交 状态 讨论区

题目描述

正如我们所知道的那样,Jack Sparrow不仅仅是一名海盗,同时他也是一名出色的数学家。

在Jack击败EIC(东印度公司)和Davy Jones后,Jack 拥有了众多的船只。

这些船只可粗略的分为两大类:一类来自EIC,一类来自Davy Jones(注意,两者可能有交集)。而Jack将这两类船只抽象为两个集合:集合E,集合D。

管理众多的船只时,往往需要一种很繁琐的集合操作:α。对于集合操作α,Jack定义为: E α D=E∪D-E∩D。

ok,现在Jack需要取出集合对{A,B},并且满足: A∈E B∈D 使得: (A α E)α(B α D)=E α D,其中A,B都是集合。

例如:E={1},D={1,2},那么EαD = {2},符合条件的{A,B}共有2种。

Jack需要知道的是,这样的集合对存在多少?答案对1e9+7取模。

输入

输入包含多组测试数据,每组数据包含三个正整数 L1,L2,L3(L1,L2,L3 <= 1e18),分别表示|E|,|D|,|E∩D|。


输出

输入答案,答案对1e9+7取模。

样例输入

复制
1 2 1

样例输出

复制
2

提示


			

来源

声声醉如兰