#pragma warning(disable:4786)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<functional>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<utility>
#include<fstream>
#include<sstream>
#include<cmath>
#include<stack>
#include<cstdio>
#include <ctime>


using namespace std;

#define MEM(a,b) memset(a,(b),sizeof(a))
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b)  ((a) < (b) ? (a) : (b))
#define istr(S) istringstream sin(S)
#define MP make_pair
#define pb push_back
#define inf 1000000000

#define M 1000003

typedef long long LL;
//typedef __int64 LL;

typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<pi> vpi;

LL arr[105];
int fact[M],ifact[M];
int digs[100],n;

int conv(LL n,int p)
{
	int i,j,tot=0;

	if(n==0) digs[tot++]=0;

	while(n)
	{
		digs[tot++]=n%p;
		n/=p;
	}
	//reverse(digs,digs+tot);
	return tot;
}

LL modexp(LL a,LL b,LL c)
{
	if(b==0) return 1%c;
	if(b%2) return ((a%c)*modexp(a,b-1,c))%c;
	LL q=modexp(a,b/2,c);
	return (q*q)%c;
}

LL nck2(int n,int k)
{
	if(n<k) return 0;
	LL ret=fact[n];
	ret=(ret*ifact[k])%M;
	ret=(ret*ifact[n-k])%M;
	return ret;

}

LL nck(LL n,int k)
{
	if(n/M==0) return nck2(n,k);
	return nck(n/M,k);
}


LL gcd(LL a,LL b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}


LL prod[105];

int main()
{
	int i,j,k,tests,cs=0,p;
	LL n,K;

	fact[0]=ifact[0]=1;
	for(i=1;i<M;i++)
	{
		fact[i]=((LL)fact[i-1]*i)%M;
		ifact[i]=modexp(fact[i],M-2,M);
	}

	scanf("%d",&tests);
	while(tests--)
	{
		//scanf("%I64d%I64d%d",&n,&K,&p);
		scanf("%lld%lld%d",&n,&K,&p);

		if(n==0)
		{
			puts("1");
			continue;
		}

		LL lp1=nck(K+p-1,p-1),lp=1;

		int m=conv(n+1,p);
		LL inv=modexp(K,M-2,M);
		LL ans=0;

		for(i=m-1;i>=0;i--)
		{
			prod[i]=nck(digs[i]+K-1,digs[i]);
			if(i!=m-1)
				prod[i]=(prod[i]*prod[i+1])%M;
		}

		for(k=0;k<m;k++)
		{
			LL q=(lp*digs[k])%M;
			q=(q*inv)%M;
			q=(q*prod[k])%M;

			ans=(ans+q)%M;
			lp=(lp*lp1)%M;
		}

	//	printf("%I64d\n",ans);
		printf("%lld\n",ans);

	}

	return 0;
}