#### Registered Users Only

Please login to view and utilize this feature.

## Problem Description

Pwynut loves to waste time walking in a 2 dimensional square grid. He can walk to any adjacent square sharing a side within 1 unit of time. Today, he feels like wasting 2n units of time walking.

He is currently at (0,0) and he wants to walk to (x,y) by taking 2n steps. Find the number of distinct paths pwynut can take to get to his destination! Note that pwynut can choose to leave the destination to return later if he arrives early. Since the answer is possibly very large, output the answer mod 1 000 000 007, a large prime number.

Your code must be able to handle multiple test cases of (n,x,y).

## Input

The first line will contain 1 integer q, indicating the number of test cases.

The next q lines will contain n, x, y each, indicating the amount of time pwynut wants to waste, and the destination of pwynut.

## Output

q lines each containing an integer, the number of distinct paths mod 1 000 000 007.

## Subtasks

Subtask 1 (12 points): q ≤ 10 , n ≤ 8 , -2n ≤ x,y ≤ 2n

Subtask 2 (17 points): q ≤ 10 , n ≤ 500 , -2n ≤ x,y ≤ 2n

Subtask 3 (32 points): q ≤ 10 , n ≤ 2000 , -2n ≤ x,y ≤ 2n

Subtask 4 (24 points): q ≤ 1 , n ≤ 1000000 , -2n ≤ x,y ≤ 2n

Subtask 5 (15 points): q ≤ 1000000 , n ≤ 1000000 , x = y = 0

## Sample Input

5 2 -1 1 2 0 0 2 1 -2 2 -2 -2 2 -3 2

## Sample Output

24 36 0 6 0

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 12 | 10 | 1s | 32MB | Minimum |

2 | 17 | 30 | 1s | 32MB | Minimum |

3 | 32 | 60 | 1s | 32MB | Minimum |

4 | 24 | 90 | 1s | 32MB | Minimum |

5 | 15 | 91 | 1s | 32MB | Minimum |

6 | 0 | 1 | 1s | 32MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o wastingtime -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512