Language: C++

#include <bits/stdc++.h>
#include <iomanip>
#define DEBUG 1

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLDLD;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<char> VB;

#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(int)(b);--i)
#define RREP(i,n) RFOR(i,n,0)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define UNQ(a) a.erase(std::unique(ALL(a)),a.end());
#define endl "\n"

#define BEGIN_STACK(size) \
	void *dummy = malloc(size); \
	void *org_stack; \
	char *my = (char *)alloca((1 + (int)(((long long)dummy) & 127)) * 16); \
	*my = 0; \
	asm volatile("mov %%rsp, %%rbx\n" \
		"mov %%rax, %%rsp" \
		: "=b"(org_stack) \
		: "a"((char *)dummy + (size)-1024));

#define END_STACK \
	asm volatile("mov %%rax, %%rsp" ::"a"(org_stack)); \
	free(dummy);

const LD EPS=1e-10;
const long long INFLL=(LL)(1e9)*(LL)(1e9);
const int INF=1e9+7;

template<class T>
void chmin(T& a, const T b)
{
	if(a>b)
		a=b;
}
template<class T>
void chmax(T& a, const T b)
{
	if(a<b)
		a=b;
}

const LL powLL(const LL p, const LL q)
{
	LL t=1;
	for(int i=0;i<q;i++)
		t*=p;
	return t;
}

template <typename T>
struct has_iter
{
	private:
		template <typename U>
		static constexpr true_type check(typename U::iterator*);
		template <typename U>
		static constexpr false_type check(...);

	public:
		static constexpr bool value = decltype(check<T>(nullptr))::value;
};


template<typename T, typename U = typename T::iterator>
void print(const T& container)
{
		auto&& first=begin(container), last=end(container);
		auto&& back=prev(last);
		for(auto e=first; e!=last; e=next(e))
			cout<<*e<<" \n"[e==back];
}


extern void* enabler;
template<typename Head, typename enable_if<!has_iter<Head>::value>::type*& = enabler>
void print(const Head& head)
{
	cout<<head<<endl;
}

template<> void print<string>(const string& container)
{
	cout<<container<<endl;
}

template<typename Head, typename... Tail>
void print(const Head& head, const Tail&... tail)
{
	cout<<head<<" ";
	print(tail...);
}

template<typename... Args>
void printd(const Args&... args)
{
	#ifdef DEBUG
		print(args...);
	#endif
}

template<typename Head>
void input(Head& head)
{
	cin>>head;
}

template<typename Head, typename... Tail>
void input(Head& head, Tail&... tail)
{
	cin>>head;
	input(tail...);
}

void io_speedup()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
}

template<typename T>
istream& operator >> (istream& is, vector<T>& vec)
{
	for(T& x: vec) is >> x;
	return is;
}


template<typename T, typename U>
istream& operator >> (istream& is, pair<T, U>& t)
{
	is>>t.first>>t.second;
	return is;
}

template<int N, typename... Ts, typename enable_if<N == sizeof...(Ts)-1>::type*& = enabler>
void tuple_in(istream &is, tuple<Ts...> &t)
{
	is>>get<N>(t);
}
template<int N, typename... Ts, typename enable_if<N < sizeof...(Ts)-1>::type*& = enabler>
void tuple_in(istream &is, tuple<Ts...> &t)
{
	is>>get<N>(t);
	tuple_in<N+1, Ts...>(is, t);
}

template<typename... Ts>
istream& operator >> (istream& is, tuple<Ts...>& t)
{
	tuple_in<0, Ts...>(is, t);
	return is;
}


template<typename T, typename U>
ostream& operator << (ostream& os, const pair<T, U>& t)
{
	os<<'('<<t.first<<", "<<t.second<<')';
	return os;
}

template<int N, typename... Ts, typename enable_if<N == sizeof...(Ts)-1>::type*& = enabler>
void tuple_out(ostream &os,const tuple<Ts...> &t)
{
	os<<get<N>(t);
}
template<int N, typename... Ts, typename enable_if<N < sizeof...(Ts)-1>::type*& = enabler>
void tuple_out(ostream &os,const tuple<Ts...> &t)
{
	os<<get<N>(t)<<", ";
	tuple_out<N+1, Ts...>(os, t);
}

template<typename... Ts>
ostream& operator << (ostream& os, const tuple<Ts...>& t)
{
	os<<'(';
	tuple_out<0, Ts...>(os, t);
	os<<')';
	return os;
}

template<typename T>
vector<T> read(int n)
{
	vector<T> t(n);
	cin>>t;
	return t;
}

template<typename T>
T read()
{
	T t;
	cin>>t;
	return t;
}

const LL MODU = 1000003;
class Mod
{
	public:
		using value_type = long long;
	private:
		static const value_type MODULO = MODU;
		value_type value;

		constexpr value_type Normalize(value_type x) const
		{
			return x<0?(x%MODULO+MODULO):(x%MODULO);
		}

	public:
		constexpr Mod():value(0){}
		constexpr Mod(const value_type &val):value(Normalize(val)) {}
		
		explicit operator value_type () const
		{
			return value;
		}

		constexpr const Mod operator -() const
		{
			return Mod(MODULO - value);
		}
		constexpr const Mod operator +(const Mod &rhs) const
		{
			return Mod(value + rhs.value);
		}
		constexpr const Mod operator -(const Mod &rhs) const
		{
			return Mod(value + (-rhs).value);
		}
		constexpr const Mod operator *(const Mod &rhs) const
		{
			return Mod(value * rhs.value);
		}
		Mod &operator +=(const Mod &rhs)
		{
			return *this = *this + rhs;
		}
		Mod &operator -=(const Mod &rhs)
		{
			return *this = *this - rhs;
		}
		Mod &operator *=(const Mod &rhs)
		{
			return *this = *this * rhs;
		}


		Mod pow(value_type p) const;

		Mod inv() const
		{
			return pow(MODULO-2);
		}

		const Mod operator /(const Mod &rhs) const
		{
			return *this * rhs.inv();
		}
		Mod &operator /=(const Mod &rhs)
		{
			return *this = *this / rhs;
		}  
		constexpr bool operator ==(const Mod &rhs)
		{
			return value == rhs.value;
		}
};

Mod Mod::pow(value_type p) const
{
	Mod tmp=1, mult=*this;
	while(p)
	{
		if((p&1)>0) tmp*=mult;
		p>>=1;
		mult*=mult;
	}
	return tmp;
}

namespace std
{
	ostream& operator<<(ostream& os, const Mod mod)
	{
		os<<(typename Mod::value_type)mod;
		return os;
	}
};

class Factorial
{
	private:
		vector<Mod> ary;
	public:
		explicit Factorial(const size_t size):ary(vector<Mod>(size))
		{
			ary[0]=1;
			for(size_t i=1;i<size;i++)
				ary[i]=ary[i-1]*i;
		}

		size_t size() const {   return ary.size();  }

		Mod operator[] (const int id) const
		{
			return ary[id];
		}
};
class FactorialInv
{
	private:
		vector<Mod> ary;
	public:
		explicit FactorialInv(const Factorial &fact):ary(vector<Mod>(fact.size()))
		{
			for(size_t i=0;i<ary.size();i++)
				ary[i]=fact[i].inv();
		}

		//FactorialInv& operator=(FactorialInv&&)=default;

		Mod operator[] (const int id) const
		{
			return ary[id];
		}
};

class Combination
{
	private:
		const Factorial *fact;
		const FactorialInv *fact_inv;
	public:
		Combination(const Factorial &fact_, const FactorialInv &fact_inv_):fact(&fact_),fact_inv(&fact_inv_)
		{}

		Mod operator()(const int n, const int m) const
		{
			return (*fact)[n] * (*fact_inv)[m] * (*fact_inv)[n-m];
		}
};



int main()
{
	using VM=vector<Mod>;
	Factorial fact(4000010);
	int q=read<int>();
	REP(i,q)
	{
		LL xx, dd, nn;
		cin>>xx>>dd>>nn;
		if(xx==0)
		{
			print(0);
			continue;
		}
		Mod x=xx, d=dd;
		if(dd==0)
		{
			print(x.pow(nn%MODU));
			continue;
		}
		Mod p=x/d-1;
		if(p+nn>=MODU)
		{
			print(0);
			continue;
		}
		Mod t=fact[nn+(LL)(p)]/fact[(LL)p];
		//printd(p,t,t*d.pow(nn));
		t*=d.pow(nn);
		print(t);
	}
}

Compiler output:
a.cc: In function 'int main()':
a.cc:385:24: error: no match for 'operator>=' (operand types are 'const Mod' and 'const LL' {aka 'const long long int'})
  385 |                 if(p+nn>=MODU)
      |                    ~~~~^~~~~~
      |                     |    |
      |                     |    const LL {aka const long long int}
      |                     const Mod
a.cc:385:24: note: candidate: 'operator>=(long long int, LL {aka long long int})' (built-in)
  385 |                 if(p+nn>=MODU)
      |                    ~~~~^~~~~~
a.cc:385:24: note:   no known conversion for argument 1 from 'const Mod' to 'long long int'
In file included from /usr/include/c++/14/regex:68,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:181,
                 from a.cc:1:
/usr/include/c++/14/bits/regex.h:1165:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator>=(const sub_match<_BiIter>&, const sub_match<_BiIter>&)'
 1165 |     operator>=(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1165:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   'const Mod' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
/usr/include/c++/14/bits/regex.h:1248:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator>=(__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const sub_match<_BiIter>&)'
 1248 |     operator>=(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1248:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   'const Mod' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
/usr/include/c++/14/bits/regex.h:1341:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator>=(const sub_match<_BiIter>&, __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1341 |     operator>=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1341:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   'const Mod' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
/usr/include/c++/14/bits/regex.h:1415:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>=(const typename std::iterator_traits<_Iter>::value_type*, const sub_match<_BiIter>&)'
 1415 |     operator>=(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1415:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'const LL' {aka 'const long long int'}
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
/usr/include/c++/14/bits/regex.h:1509:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>=(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1509 |     operator>=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1509:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   'const Mod' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
/usr/include/c++/14/bits/regex.h:1586:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>=(const typename std::iterator_traits<_Iter>::value_type&, const sub_match<_BiIter>&)'
 1586 |     operator>=(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1586:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'const LL' {aka 'const long long int'}
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
/usr/include/c++/14/bits/regex.h:1686:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>=(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1686 |     operator>=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1686:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   'const Mod' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51:
/usr/include/c++/14/bits/stl_pair.h:1070:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator>=(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1070 |     operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1070:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   'const Mod' is not derived from 'const std::pair<_T1, _T2>'
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:476:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator>=(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  476 |     operator>=(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:476:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   'const Mod' is not derived from 'const std::reverse_iterator<_Iterator>'
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
/usr/include/c++/14/bits/stl_iterator.h:520:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator>=(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  520 |     operator>=(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:520:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   'const Mod' is not derived from 'const std::reverse_iterator<_Iterator>'
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
/usr/include/c++/14/bits/stl_iterator.h:1724:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator>=(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1724 |     operator>=(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1724:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   'const Mod' is not derived from 'const std::move_iterator<_IteratorL>'
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
/usr/include/c++/14/bits/stl_iterator.h:1781:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator>=(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)'
 1781 |     operator>=(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1781:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   'const Mod' is not derived from 'const std::move_iterator<_IteratorL>'
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
In file included from /usr/include/c++/14/bits/basic_string.h:47,
                 from /usr/include/c++/14/string:54,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52:
/usr/include/c++/14/string_view:739:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator>=(basic_string_view<_CharT, _Traits>, basic_string_view<_CharT, _Traits>)'
  739 |     operator>=(basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/14/string_view:739:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   'Mod' is not derived from 'std::basic_string_view<_CharT, _Traits>'
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
/usr/include/c++/14/string_view:746:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator>=(basic_string_view<_CharT, _Traits>, __type_identity_t<basic_string_view<_CharT, _Traits> >)'
  746 |     operator>=(basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/14/string_view:746:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   'Mod' is not derived from 'std::basic_string_view<_CharT, _Traits>'
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
/usr/include/c++/14/string_view:754:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator>=(__type_identity_t<basic_string_view<_CharT, _Traits> >, basic_string_view<_CharT, _Traits>)'
  754 |     operator>=(__type_identity_t<basic_string_view<_CharT, _Traits>> __x,
      |     ^~~~~~~~
/usr/include/c++/14/string_view:754:5: note:   template argument deduction/substitution failed:
a.cc:385:26: note:   mismatched types 'std::basic_string_view<_CharT, _Traits>' and 'long long int'
  385 |                 if(p+nn>=MODU)
      |                          ^~~~
/usr/include/c++/14/bits/basic_string.h:3997:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>=(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 3997 |     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:3997:5: