Description

小A和小B是一对好朋友，他们经常一起愉快的玩耍。最近小B沉迷于**师手游，天天刷本，根本无心搞学习。但是

已经入坑了几个月，却一次都没有抽到SSR，让他非常怀疑人生。勤勉的小A为了劝说小B早日脱坑，认真学习，决

定以抛硬币的形式让小B明白他是一个彻彻底底的非洲人，从而对这个游戏绝望。两个人同时抛b次硬币，如果小A

的正面朝上的次数大于小B正面朝上的次数，则小A获胜。但事实上，小A也曾经沉迷过拉拉游戏，而且他一次UR也

没有抽到过，所以他对于自己的运气也没有太大把握。所以他决定在小B没注意的时候作弊，悄悄地多抛几次硬币

，当然，为了不让小B怀疑，他不会抛太多次。现在小A想问你，在多少种可能的情况下，他能够胜过小B呢？由于

答案可能太大，所以你只需要输出答案在十进制表示下的最后k位即可。

solution

正解：扩展卢卡斯

因为 \(a-b\) 很小，考虑怎么把式子变成和 \(a-b\) 有关.

考虑 \(a=b\) 的情况，考虑结果只有输赢和平局三种，而且输赢是对称的，所以减去平局就是答案，所以答案为 \((2^{a+b}-C(2a,a))/2\).

\(a>b\) 时，同样存在对称性，对于正着会输，反过来就赢得情况，就是 \(2^{a+b}/2\) 种

对于正着反着都赢的情况还没有算进去:

对于除2，根据对称性，只算一半即可，注意偶数情况，存在一项需要手动除2，算2时在因子中减去，算5时直接乘逆元即可

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

typedef long long ll;

const int N=2500005;

ll qm(ll x,ll k,ll MO){

    ll sum=1;

    while(k){

        if(k&1)sum*=x,sum%=MO;

        x*=x;x%=MO;k>>=1;

    }

    return sum;

}

ll v[2][N],mod,K;

void priwork(){

    int lim=qm(2,9,N);

    v[0][0]=v[1][0]=1;

    for(RG int i=1;i<=lim;i++){

        v[0][i]=v[0][i-1]*((i&1)?i:1);

        v[0][i]%=lim;

    }

    lim=qm(5,9,N);

    for(RG int i=1;i<=lim;i++){

        v[1][i]=v[1][i-1]*((i%5)?i:1);

        v[1][i]%=lim;

    }

}

inline void exgcd(ll a,ll b,ll &x,ll &y){

    if(!b)x=1,y=0;

    else exgcd(b,a%b,y,x),y-=a/b*x;

}

inline ll ni(ll a,ll b){

    ll x,y;

    exgcd(a,b,x,y);

    x%=b;if(x<0)x+=b;

    return x;

}

inline ll Fac(ll n,ll p,ll pr){

    if(n==0)return 1;

    ll re=v[p!=2][pr]%pr;

    re=qm(re,n/pr,pr);

   ll r=n%pr;

    re=re*v[p!=2][r]%pr;

    return re*Fac(n/p,p,pr)%pr;

}

inline ll C(ll n,ll m,ll p,ll pr,bool t){

    if(n<m)return 0;

    ll c=0;

    for(RG ll i=n;i;i/=p)c+=(i/p);

    for(RG ll i=m;i;i/=p)c-=(i/p);

    for(RG ll i=n-m;i;i/=p)c-=(i/p);

    if(t && p==2)c--;

  	if(c>=K)return 0;

    ll x=Fac(n,p,pr),y=Fac(m,p,pr),z=Fac(n-m,p,pr);

    ll re=x*ni(y,pr)%pr*ni(z,pr)%pr*qm(p,c,pr)%pr;

    if(t && p==5)re=re*ni(2,pr)%pr;

    return (mod/pr)*ni(mod/pr,pr)%mod*re%mod;

}

inline ll lucas(ll n,ll m,ll k,bool t){

    ll MOD=qm(2,k,N),re=0;

    re=(re+C(n,m,2,MOD,t))%mod;

    MOD=qm(5,k,N);

    re=(re+C(n,m,5,MOD,t))%mod;

    return re;

}

ll work(ll n,ll m,ll k)

{

    ll ans=0;mod=qm(10,k,1e9+5);

    if(n==m)

         return ((qm(2,n+m-1,mod)-lucas(n+m,n,k,1))%mod+mod)%mod;

    for(ll i=(n+m)/2+1;i<n;i++){

        ans+=lucas(n+m,i,k,0);

        ans%=mod;

    }

    if((n+m)%2==0)ans=(ans+lucas(n+m,(n+m)/2,k,1)%mod+mod)%mod;

   return (qm(2,n+m-1,mod)+ans)%mod;

}

inline void Print(ll x,ll c){

    if(c==1)printf("%lld\n",x);if(c==2)printf("%02lld\n",x);

    if(c==3)printf("%03lld\n",x);if(c==4)printf("%04lld\n",x);

    if(c==5)printf("%05lld\n",x);if(c==6)printf("%06lld\n",x);

    if(c==7)printf("%07lld\n",x);if(c==8)printf("%08lld\n",x);

    if(c==9)printf("%09lld\n",x);

}

int main()

{

    priwork();

    ll a,b,c,d;

    while(~scanf("%lld%lld%lld",&a,&b,&c)){

        K=c;d=work(a,b,c);

        Print(d,c);

    }

    return 0;

}