import std.stdio;
import std.algorithm;
import std.math;
import std.conv;
import std.string;

T readNum(T)(){
  return readStr.to!T;
}

T[] readNums(T)(){
  return readStr.split.to!(T[]);
}

string readStr(){
  return readln.chomp;
}

void main(){
  int q = readNum!int;

  foreach(i; 0 .. q){
    auto p = readNums!long;
    real a = p[0] * (p[0] + (p[2] - 1) * p[1]);

    real ret = 1;
    foreach(j; 0 .. p[2]/2){
      ret *= a + j * (p[2]-j-1) * p[1] * p[1];
      ret %= 1000003;
    }

    if(p[2] % 2 == 1){
      ret *= p[0] + p[1] * (p[2] / 2 + 3);
      ret %= 1000003;
    }

    writeln(ret);
  }
}
