#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 40;
const ll inf = 1e9 + 1;

ll pi, mod; int e;
inline void add(ll &a, const ll &b) { a += b; if (a >= mod) a -= mod; }
inline ll mul(ll a, ll b)
{
    if (a < inf && b < inf) return a * b % mod;
    if (a < b) swap(a, b);
    ll re = 0;
    for (; b; b >>= 1, add(a, a)) if (b & 1ll)
        add(re, a);
    return re;
}
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
void exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!a) { x = 0, y = 1; return; }
    ll tx, ty; exgcd(b % a, a, tx, ty);
    x = ty - mul(b / a, tx); if (x < 0) x += mod;
    y = tx;
}
ll pw(ll x, ll k)
{
    ll re = 1ll;
    for (; k; k >>= 1, x = mul(x, x)) if (k & 1ll)
        re = mul(re, x);
    return re;
}
ll inv(ll x) { return pw(x, mod / pi * (pi - 1ll) - 1ll); }
struct Poly
{
    int len; ll a[maxn];
    Poly() { len = 0; memset(a, 0, sizeof a); }
    friend inline Poly operator +(const Poly &x, const Poly &y)
    {
        Poly re; re.len = max(x.len, y.len);
        for (int i = 0; i <= re.len; i++) re.a[i] = (x.a[i] + y.a[i]) % mod;
        return re;
    }
    friend inline Poly operator -(const Poly &x, const Poly &y)
    {
        Poly re; re.len = max(x.len, y.len);
        for (int i = 0; i <= re.len; i++) re.a[i] = (x.a[i] - y.a[i] + mod) % mod;
        while (re.len && !re.a[re.len]) re.len--;
        return re;
    }
    friend inline Poly operator *(const Poly &x, const Poly &y)
    {
        Poly re; re.len = min(x.len + y.len, e - 1);
        for (int i = 0; i <= x.len; i++) for (int j = 0; j <= y.len && i + j < e; j++)
            add(re.a[i + j], mul(x.a[i], y.a[j]));
        return re;
    }
};

ll n, m; int K;
ll num2, num5, num0;
void calp(ll p1, ll N, ll &num, ll sig) { for (ll i = p1; i <= N; i *= p1) num += sig * (N / i); }
void Calp()
{
    calp(2ll, n + m, num2, 1ll); calp(2ll, n, num2, -1ll); calp(2ll, m, num2, -1ll);
    calp(5ll, n + m, num5, 1ll); calp(5ll, n, num5, -1ll); calp(5ll, m, num5, -1ll);
    num0 = min(num2, num5);
}
ll sum[1100], C[maxn][maxn];
ll cal(ll N)
{
    if (N < 1100) return sum[N];
    ll u = N / pi;
    Poly re; re.len = 0, re.a[0] = 1;
    Poly x = re;
    for (ll i = 1; i < pi; i++) 
    {
        Poly y; y.len = 1; y.a[0] = i % mod, y.a[1] = 1;
        x = x * y;
    }
    ll k = u, now = 0, xp = 1ll;
    for (; k; k >>= 1, xp <<= 1)
    {
        if (k & 1ll)
        {
            Poly temp; temp.len = x.len;
            ll nowq = now * pi % mod;
            for (int i = 0; i <= x.len; i++) 
            {
                ll tc = 1ll;
                for (int j = i; j >= 0; j--, tc = mul(tc, nowq))
                    add(temp.a[j], mul(x.a[i], mul(tc, C[i][j])));
            }
            re = re * temp; now += xp;
        }
        Poly temp2; temp2.len = x.len;
        ll xq = xp * pi % mod;
        for (int i = 0; i <= x.len; i++)
        {
            ll tc = 1ll;
            for (int j = i; j >= 0; j--, tc = mul(tc, xq))
                add(temp2.a[j], mul(x.a[i], mul(tc, C[i][j])));
        }
        x = x * temp2;
    }

    ll ans = re.a[0]; for (ll i = u * pi + 1ll; i <= N; i++) ans = mul(ans, i % mod);
    return mul(ans, cal(N / pi));
}
ll solve(ll p1, ll p2)
{
    if (p1 == 2ll && num2 - num0 >= K) return 0;
    if (p1 == 5ll && num5 - num0 >= K) return 0;
    pi = p1, mod = p2;

    sum[0] = 1ll; 
    for (int i = 1; i < 1100; i++)
    {
        ll ti = i; while (ti % pi == 0) ti /= pi;
        sum[i] = mul(sum[i - 1], ti);
    }
    C[0][0] = 1ll;
    for (int i = 1; i < maxn; i++)
    {
        C[i][0] = 1ll;
        for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }

    ll re = cal(n + m); 
    re = mul(re, inv(cal(n))); re = mul(re, inv(cal(m)));
    if (p1 == 2ll) re = mul(re, pw(2ll, num2 - num0)), re = mul(re, inv(pw(5ll, num0)));
    else re = mul(re, pw(5ll, num5 - num0)), re = mul(re, inv(pw(2ll, num0)));
    return re;
}

void print(ll x)
{
    ll tmp = mod / 10ll;
    while (x < tmp) putchar('0'), tmp /= 10;
    printf("%lld\n", x);
}

int main()
{
    // freopen("tmp.in", "r", stdin);
    // freopen("tmp.out", "w", stdout);

    scanf("%lld%lld%d", &n, &m, &K); e = K;
    Calp();
    ll A = 1, B = 1; for (int i = 1; i <= K; i++) A *= 2ll, B *= 5ll;
    ll a = solve(2ll, A), b = solve(5ll, B);
    ll x, y; mod = A * B; exgcd(A, B, x, y);
    x = mul(x, (b - a + mod) % mod);
    x = mul(A, x); add(x, a);
    print(x);

    return 0;
}