Nam loves animals. That's why he raised a lot of pets: D dogs and C cats. Dogs keep his house away from thief, while cats chase mice. Hence, one day Nam put all his pets in a straight line to give them candies. The first D pets are dogs and the last C pets are cats.

To avoid fight between dogs and cats, giving candies to them must be satisfied conditions:

1. Every pet should be given at least one candy and at most N candies.
2. Sum of all candies given to D dogs must be equal to sum of all candies given to C cats.

Nam finds it easy to give pets candies to satisfy the conditions above. However, he can't calculate the number of ways to do it. Two ways are considered different if there exists a pet that received different number of candies in these two candies' distributions.

Input

First line is T - the number of test cases.

T lines follow, each line is a description of a test case consisting of three positive integers D, C and N.

Output

Consists of T lines, each line is the number of ways to give the candies to Nam's pets. You should print the answer modulo 1000003 (10⁶ + 3).

Constraints

• 1 ≤ T ≤ 10;
• 1 ≤ D, C, N ≤ 10⁶
• 30% number of tests in which 1 ≤ D, C, N ≤ 20
• 20% number of tests in which 1 ≤ D, C, N ≤ 50
• 20% number of tests in which 1 ≤ D, C, N ≤ 1000