let modulo = 1000003
let (+^) a b = (a + b) mod modulo
let ( *^) a b = (a * b) mod modulo
let rec ( ** ) a n =
  if n = 0 then 1
  else if n mod 2 = 1 then a *^ a ** (n-1)
  else let h = a ** (n/2) in h *^ h
let inv x = x ** (modulo-2)
let (/^) a b = a *^ inv b

let fact, facti =
  let fact = Array.make 1000003 1 in
  let facti = Array.make 1000003 1 in
  for i = 1 to 1000002 do
    fact.(i) <- i *^ fact.(i-1);
    facti.(i) <- inv fact.(i)
  done;
  fact, facti

let solve x d n =
  if d = 0 then x**n else 
  let y0 = x /^ d in
  if y0+n-1 >= modulo then 0
  else d**n *^ fact.(y0+n-1) *^ facti.(y0-1)

let () =
  Scanf.scanf "%d" @@ fun q ->
  for i = 1 to q do Scanf.scanf " %d %d %d" solve |> Printf.printf "%d\n" done
