#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template<typename T> using rev_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class S, class T> void map_init(map<S, T> &m, S k, T v){if(!m.count(k)) m[k] = v;}
void R_YESNO(bool p) { cout << (p ? "YES" : "NO") << endl; }
void R_YesNo(bool p) { cout << (p ? "Yes" : "No") << endl; }

const i64 MOD = 1e6 + 3;

/*!* [modint] *!*/
/*+* 剰余環整数 *+*/
struct int_m;
int_m invmod(int_m);
int_m powmod(int_m, i64);
struct int_m {
    static i64 m;
    i64 v;
    int_m() {}
    int_m(i64 x) : v(x) {}
    int_m operator+(const int_m &y) const { return (v + y.v) % m; }
    int_m operator-(const int_m &y) const { return (v - y.v + m) % m; }
    int_m operator*(const int_m &y) const { return (v * y.v) % m; }
    int_m operator/(const int_m &y) const { return *this * invmod(y); }
    int_m operator^(const i64   &y) const { return powmod(*this, y); }
    void operator+=(const int_m &y) { *this = *this + y; }
    void operator-=(const int_m &y) { *this = *this - y; }
    void operator*=(const int_m &y) { *this = *this * y; }
    void operator/=(const int_m &y) { *this = *this / y; }
    void operator^=(const i64   &y) { *this = *this ^ y; }
    bool operator==(const int_m &y) const { return v == y.v; }
    bool operator!=(const int_m &y) const { return v != y.v; }
    friend istream &operator>>(istream &ist, int_m &m) { ist >> m.v; return ist; }
    friend ostream &operator<<(ostream &ost, int_m &m) { ost << m.v; return ost; }
};
i64 int_m::m;
// O(log a)
int_m powmod(int_m a, i64 p) {
    int_m v = 1;
    for(int_m b = a; p > 0; p >>= 1, b *= b ) if(p & 1) v *= b;
    return v;
}
int_m invmod(int_m x) {
    return powmod(x, x.m - 2);
}
struct ModFact {
    static vector<int_m> val, inv;
    static void Init(int N) { // O(N)
        val = vector<int_m>(++N, 1), inv = vector<int_m>(N, 1);
        for(int i = 1; i < N; i++) val[i] = val[i - 1] * i;
        inv[N - 1] = invmod(val[N - 1]);
        for(int i = N - 1; i > 0; i--) inv[i - 1] = inv[i] * i;
    }
};
vector<int_m> ModFact::val, ModFact::inv;
int_m Permutation(int n, int m) {
    if(n < m || m < 0 || n < 0) return 0;
    return ModFact::val[n] * ModFact::inv[n - m];
}
int_m Combination(int n, int m) {
    if(n < m || m < 0 || n < 0) return 0;
    return ModFact::val[n] * ModFact::inv[m] * ModFact::inv[n - m];
}
int_m Combination(vector<int> &n) {
    int s = accumulate(n.begin(), n.end(), 0);
    int_m r = ModFact::val[s];
    for(auto x : n) r *= ModFact::inv[x];
    return r;
}
int_m Multichoose(int n, int m) { return Combination(n + m - 1, m); }
// 剰余多項式
struct MPoly {
    vector<int_m> c;
    int sz() const { return c.size(); }
    int deg() const { return sz() - 1; }
    MPoly operator+(const MPoly &p) const {
        MPoly x;
        int N = sz(), M = p.sz();
        for(int i = max(N, M) - 1; i >= 0; i--) {
            int_m tmp = 0;
            if(i < N) tmp += c[i];
            if(i < M) tmp += p.c[i];
            if(tmp != 0) {
                if(x.c.empty()) x.c.resize(i + 1);
                x.c[i] = tmp;
            } else {
                if(!x.c.empty()) x.c[i] = 0;
            }
        }
        return x;
    }
    MPoly operator*(int_m t) const {
        MPoly x;
        x.c.resize(sz());
        for(int i = 0; i < sz(); i++) x.c[i] = c[i] * t;
        return x;
    }
    MPoly operator-() {
        return (*this) * int_m(-1);
    }
    MPoly operator-(const MPoly &p) {
        return (*this) + (p * (int_m)(-1));
    }
    MPoly operator*(const MPoly &p) const {
        MPoly x;
        x.c.resize(p.sz() + sz() - 1);
        for(int i = 0; i < x.sz(); i++) {
            int_m tmp = 0;
            for(int j = 0; j < p.sz(); j++) {
                tmp += p.c[j] * c[i - j];
            }
        }
    }
    MPoly operator*(const int_m &t) {
        MPoly x;
        x.c.resize(sz());
        for(int i = 0; i < sz(); i++) {
            x.c[i] = t * c[i];
        }
        return x;
    }
};

int main() {
    int_m::m = MOD;
    int Q;
    cin >> Q;
    ModFact::Init(MOD - 1);
    for(int q = 0; q < Q; q++) {
        int_m x, d, ans;
        i64 n;
        cin >> x >> d >> n;
        if(d == 0) {
            ans = x ^ n;
        } else {
            i64 t = (x / d).v;
            ans = MOD < t + n ? 0 : Permutation(t + n - 1, n);
            ans *= d ^ n;
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 18560