CODESPTH - Polygon Diagonals

no tags 

Consider a regular polygon with N vertices labelled 1..N. In how many ways can you draw K diagonals such that no two diagonals intersect at a point strictly inside the polygon? A diagonal is a line segment joining two non adjacent vertices of the polygon.
Input:
The first line contains the number of test cases T. Each of the next T lines contain two integers N and K.
Output:
Output T lines, one corresponding to each test case. Since the answer can be really huge, output it modulo 1000003.
Constraints:
1 <= T <= 10000
4 <= N <= 10^9
1 <= K <= N
Sample Input:
3
4 1
5 2
5 3
Sample Output:
2
5
0
Explanation:
For the first case, there are clearly 2 ways to draw 1 diagonal - 1 to 3, or 2 to 4. (Assuming the vertices are labelled 1..N in cyclic order).
For the third case, at most 2 non-intersecting diagonals can be drawn in a 5-gon, and so the answer is 0.

Consider a regular polygon with N vertices labelled 1..N. In how many ways can you draw K diagonals such that no two diagonals intersect at a point strictly inside the polygon? A diagonal is a line segment joining two non adjacent vertices of the polygon.

Input:

The first line contains the number of test cases T. Each of the next T lines contain two integers N and K.

Output:

Output T lines, one corresponding to each test case. Since the answer can be really huge, output it modulo 1000003.

Constraints:

1 <= T <= 10000

4 <= N <= 10^9

1 <= K <= N

Sample Input:

3

4 1

5 2

5 3

Sample Output:

2

5

0

Explanation:

For the first case, there are clearly 2 ways to draw 1 diagonal - 1 to 3, or 2 to 4. (Assuming the vertices are labelled 1..N in cyclic order).

For the third case, at most 2 non-intersecting diagonals can be drawn in a 5-gon, and so the answer is 0.

 



Added by:Varun Jalan
Date:2011-10-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem used for CodeSprint - InterviewStreet Contest