zznu 2081 : 舰队管理

题目描述

正如我们所知道的那样，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


形象表示一下这个自定义符号运算α

E α D=（除去图中阴影部分）

由 A∈E B∈D，得

A α E=E-A；B α D=D-B；

(A α E)α(B α D)=E α D，要想使得等式成立，A和B必须在阴影部分取（也就是两个集合的交集）并且A和B的元素要相同。

用集合论来说就是求E和D交集的幂集元素个数，也就是2^L3（L3表示E和D交集元素个数）

换种方式说就是就排列组合数

还有一点需要注意的是指数比较大，需要用到快速幂。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;
#define LL long long
#define INT 0x7fffffff
LL mod=1e9+7;
LL quick_pow(LL n, LL k)
{
    LL ans=1;
    n=n%mod;
    while(k)
    {
        if(k&1)
            ans=ans*n%mod;
        n=n*n%mod;
        k/=2;
    }
    return ans;
}
int main()
{
    LL r1, r2, r3;
    while(scanf("%lld%lld%lld", &r1, &r2, &r3)!=EOF)
    {
        LL ans=quick_pow((LL)2, r3);
        printf("%lld\n", ans);
    }
    return 0;
}