rt，exlucas套的板子

//P3726
#include <algorithm>
#include <iostream>
#include <cstring>
#include <utility>
#include <complex>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
template<typename T> inline T read(); // int a = read<int>();
template<typename T> inline void write(T x); // write(a); put ' ';
template<typename T> inline void writen(T x); // write(a); put '\n';
#define RAND(l, r) ((ll)rand()*rand()*rand()%(r-l+1)+l)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++ i)
#define debug printf("----------");
#define rdll read<long long>()
#define lowbit(x) ((x)&-(x))
#define rdi read<int>()
#define endl puts("");
template<typename T> inline T read(){
	T x = 0;
	bool flg = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') flg = 0;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		x = (x<<1) + (x<<3) + ch - '0';
		ch = getchar();
	}
	if(flg) return x;
	return ~ (x-1);
}
template<typename T> inline void write(T x){
	if (x < 0){
		putchar('-');
		x = ~ (x-1);
	}
	int s[100], top = 0;
	while(x){
		s[++top] = x % 10;
		x /= 10;
	}
	if(!top){
		s[++top] = 0;
	}
	while(top){
		putchar(s[top--] + '0');
	}
	putchar(' ');
	return;
}
template<typename T> inline void writen(T x){
	if (x < 0){
		putchar('-');
		x = ~ (x-1);
	}
	int s[100], top = 0;
	while(x){
		s[++top] = x % 10;
		x /= 10;
	}
	if(!top){
		s[++top] = 0;
	}
	while(top){
		putchar(s[top--] + '0');
	}
	endl;
	return;
}
namespace PetitSouris_AK_IOI{

// put your code here

//#define multiple_test_cases

const int N = 1e6 + 10;
ll a[N], b[N], x, y, P = 2e9; 
int tot, k;
ll qp(ll a, ll b, ll p){
	ll ans = 1;
	while(b){
		if(b & 1){
			ans = ans * a % p;
		}
		a = a * a % p;
		b >>= 1;
	}
	return ans;
}
void exgcd(ll &x, ll &y, ll a, ll b){
    if(!b){
		x = 1, y = 0;
		return;
	}
    exgcd(x, y, b, a%b);
    ll z = x; 
	x = y; 
	y = z - a / b * y;
}
ll inv(ll x, ll p){
    ll a, k;
    exgcd(a, k, x, p);
    return (a % p + p) % p;
}
ll calc(ll n, ll p, ll pk){
    if(!n){
    	return 1;
	}
	ll ans = 1;
    for(ll i = 1; i <= pk; ++ i){
    	if(i % p){
    		ans = ans * i % pk;
		}
	}
    ans = qp(ans, n/pk, pk);
    for(ll i = 1; i <= n%pk; ++i){
		if(i % p){
			ans = ans * i % pk;
		}
	}
    return ans * calc(n/p, p, pk) % pk;
}
ll C(ll n, ll m, ll p, ll pk){
    if(n == 0 || m == 0 || n == m){
    	return 1;	
	} 
	if(n < m){
		return 0;
	}
    ll nn = calc(n, p, pk), mm = calc(m, p, pk), nm = calc(n-m, p, pk);
    ll cnt = 0, k = n - m;
    while(n){
    	n /= p, cnt += n;
	}
    while(m){
    	m /= p, cnt -= m;
	}
    while(k){
    	k /= p, cnt -= k;
	}
    return nn * inv(mm, pk) % pk * inv(nm, pk) % pk *
           qp(p, cnt, pk) % pk;
}
ll CRT(){
    long long M = 1, ans = 0;
    for(int i = 1; i <= tot; ++ i){
		M *= b[i];
	}
    for(int i = 1; i <= tot; ++ i){
        ans += a[i] * (M/b[i]) * inv(M/b[i], b[i]);
	}
	tot = 0;
    return (ans % M + M) % M;
}
ll exLucas(ll n, ll m, ll p){
    for(ll i = 2; i * i <= p && p >= 1; ++ i){
        ll pk = 1;
        while(p % i == 0){
        	p /= i;
			pk *= i;
		}
        if(pk > 1){
        	a[++tot] = C(n, m, i, pk);
			b[tot] = pk;
		}
    }
    if(p > 1){
    	a[++tot] = C(n, m, p, p);
		b[tot] = p;
	}
    return CRT();
}

void print(ll ans){
	ll md = 1;
	for(int i = 1; i <= k; ++ i){
		md *= 10;
	}
	ans %= md;
	printf("%0*lld\n", k, ans);
}
void solve(){
	while(~scanf("%lld%lld%d", &x, &y, &k)){
		if(x == y){
			print((qp(2, x+y, P) - exLucas(x+x, x, P) + P) % P / 2);
		} else {
			ll sum = 0;
			for(int i = 1; i <= x-y-1; ++ i){
				sum = (sum + exLucas(x+y, y+i, P)) % P;
			}
			print((qp(2, x+y, P) + sum) % P / 2);
		}
	}
}

// and then AC the problem

}

int t = 1;

int main(){
	#ifdef multiple_test_cases
	t = rdi;
	#endif
	//PetitSouris_AK_IOI::init();
	while(t--){
		PetitSouris_AK_IOI::solve();
	}
	return ~~(0^0);
}

// Powered by INFiNiTE ENERZY
//    			-overdoze-