显然(ans=sum^a_{i=1}C^i_asum^{min(b,i-1)}_{j=1}C^j_b)但显然超时
SOL：
换一种方式来思考
(a=b)
一种失败方案翻转即成功方案，答案为（总方案-不输不赢）除以2
不输不赢(sum_{i=0}^aC_a^iC_a^i=sum_{i=0}^aC_a^iC_a^{a-i})
相当于从(2a)中选出(a)个(C_{2a}^a)
(ans=frac{2^{2a}-C_{2a}^a}2)
(a!=b)
答案为（总方案+翻面还是赢的方案数）除以二
设A正面朝上y次，B正面朝上x次
(y>x,b-x<a-y o a-b>y-x)
翻面还是赢(sum_{i=0}^bC^i_bsum_{j=1}^{a-b-1}C^{i+j}_a)
(sum^{a-b-1}_{j=1}sum_{i=0}^bC^{b-i}_{b}C^{i+j}_a=sum^{a-b-1}_{j=1}C^j_{a+b})
（这个化简可以和刚才差不多，但实际为范德蒙德卷积）
(ans=frac{2^{a+b}+sum^{a-b-1}_{j=1}C^j_{a+b}}2)
模数十的倍数，需要扩展卢卡斯
除二无逆元，只好先除(2^{a+b} o2^{a+b-1})
(sum^{a-b-1}_{j=1}C^j_{a+b})实际对称的只有当(a+b)为偶数时(C^{(a+b)/2}_{a+b})只有一项
(C_{2a}^a=C_{2a-1}^a+C_{2a-1}^{a-1}=2C_{2a-1}^a)解决
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int ksm(int x,int r,int mod){
int ret=1;
for(int i=0;(1ll<<i)<=r;i++){
if((r>>i)&1)ret=ret*x%mod;
x=x*x%mod;
}
return ret;
}
inline void exgcd(int a,int b,int &x,int &y){
if(!b){x=1;y=0;return;}
exgcd(b,a%b,x,y);
int t=y;y=x-a/b*y;x=t;
}
inline int inv(int a,int mod){
if(!a)return 0;
static int x,y;
exgcd(a,mod,x,y);
return (x%mod+mod)%mod;
}
int fac[2][2000004];
int jie(int x,int p,int pk){
if(!x)return 1;
int ret=fac[p!=2][pk];
ret=ksm(ret,x/pk,pk)*fac[p!=2][x%pk]%pk;
return ret*jie(x/p,p,pk)%pk;
}
int a,b,K,mod,ans,k2,k5;
inline int C(int d,int u,int p,int pk){
if(d<u)return 0;
int js=0;
for(int i=d;i;i/=p)js+=i/p;
for(int i=u;i;i/=p)js-=i/p;
for(int i=d-u;i;i/=p)js-=i/p;
if(js>=K)return 0;
int s1=jie(d,p,pk),s2=jie(u,p,pk),s3=jie(d-u,p,pk);
int ret=ksm(p,js,pk)*s1%pk*inv(s2,pk)%pk*inv(s3,pk)%pk;
return ret*(mod/pk)%mod*inv(mod/pk,pk)%mod;//crt
}
inline int lucas(int d,int u){
return (C(d,u,2,k2)+C(d,u,5,k5))%mod;
}
inline void init(int p,int pk){
int c=(p!=2);
fac[c][0]=1;
for(int i=1;i<=pk;i++)
if(i%p)fac[c][i]=fac[c][i-1]*i%pk;
else fac[c][i]=fac[c][i-1];
}
signed main(){
init(2,512);init(5,1953125);
while(~scanf("%lld%lld%lld",&a,&b,&K)){
mod=ksm(10,K,1e9+5);
k2=ksm(2,K,1e9+5);k5=ksm(5,K,1e9+5);
ans=ksm(2,a+b-1,mod);
if(a==b)ans=(ans-lucas((a<<1)-1,a)+mod)%mod;
else{
for(int i=(a+b)/2+1;i<a;i++)ans=(ans+lucas(a+b,i))%mod;
if((a+b)%2==0)ans=(ans+lucas(a+b-1,a+b>>1))%mod;
}
while(ans<mod/10){putchar('0');mod/=10;}
cout<<ans<<"
";
}
return (0-0);
}