var arr=readLine()!.characters.split{$0==" "}.map{Int(String($0))!}
  
var q = arr[0]

for var i in 0..<q {
	var arr=readLine()!.characters.split{$0==" "}.map{Int(String($0))!}
	var sum = 0; var x = arr[0]
  
  	sum = arr[0]
	for var j in 1..<arr[2] {
      sum = sum * (  x + arr[1] * j )
      sum = ( sum % 1000003 )
    }  
	print( sum )
}