Due to your superlative performance in online school, you've been employed by CodeVax. Your assignment is as such:

There are seats in a line. These seats must be divided into exactly cohorts to reduce the transmission of the virus. Each cohort consists of a contiguous segment of exactly seats. An arrangement of cohorts is considered to be valid if there is at least seat between any two cohorts and no cohort overlaps another.

Find the total number of valid arrangements, modulo .

#### Input Specification

The first line will contain the integer , representing the number of test cases.

The next lines will each contain the integers , and for the test case.

#### Output Specification

For each test case, output the number of valid arrangements, modulo .

#### Constraints

**Note that you will NOT be required to pass all the samples to receive points.**

##### Subtask 1 [5%]

##### Subtask 2 [15%]

##### Subtask 3 [80%]

No additional constraints.

#### Sample Input 1

```
4
3 1 1
3 1 2
1 1 2
4 1 2
```

#### Sample Output 1

```
3
1
0
3
```

#### Explanation for Sample 1

Let `x`

represent the spots in the line where the cohorts are and let `-`

represent empty spaces in the line:

For the first test case, the valid cohort arrangements are: `x--`

, `-x-`

, and `--x`

.

For the second test case, the only valid cohort arrangement is: `x-x`

.

For the third test case, there are no valid cohort arrangements.

For the fourth test case, the valid cohort arrangements are: `x-x-`

, `x--x`

, and `-x-x`

.

#### Sample Input 2

```
2
111 22 9
400 25 6
```

#### Sample Output 2

```
0
586572619
```

## Comments