#include <fstream>
using namespace std;
ifstream fin("xnumere.in");
ofstream fout("xnumere.out");
int const N = 1e5 + 3 , mod = 666013;
typedef long long ll;
int x;
ll n , k;
int fact[N];
int add(ll x , ll y){
    return (x + y + mod) % mod;
}
int mul(ll x , ll y){
    return x * y % mod;
}
int lgp(ll x , ll y){
    int r = 1 , c = x;
    for(int i = 0 ; (1ll << i) <= y ; ++ i){
        if((1ll << i) & y)
            r = mul(r , c);
        c = mul(c , c);
    }
    return r;
}
int comb(int _n , int _k){
    return mul(fact[_n] , mul(lgp(fact[_k] , mod - 2) , lgp(fact[_n - _k] , mod - 2)));
}
int main()
{
    fin >> k >> x >> n;
    fact[0] = 1;
    for(int i = 1 ; i <= x ; ++ i){
        fact[i] = mul(fact[i - 1] , i);
    }
    int ans = 0;
    for(int i = 0 ; i < x ; ++ i){
        int semn = (i % 2 ? -1 : 1);
        ans = add(ans , semn * mul(comb(x , i) , lgp(x - i , n)));
    }
    ans = mul(ans , lgp(fact[x] , mod - 2));
    for(int i = 0 ; i < x ; ++ i)
        ans = mul(ans , add(k , -i));
    fout << ans << '\n';
    return 0;
}