- All Contests
- ProjectEuler+
- Project Euler #205: Dice Game

# Project Euler #205: Dice Game

# Project Euler #205: Dice Game

_{This problem is a programming version of Problem 205 from projecteuler.net}

Peter has -sided dice, each with faces numbered .

Colin has -sided dice, each with faces numbered .

Both Peter's and Colin's dice are uniform and fair for each die every outcome occurs with the equal probability of in Peter's case and in Colin's case.

Peter and Colin roll their dice and compare totals: the highest total wins. The result is a draw if the totals are equal.

What is the probability that -sided Pete beats -sided Colin? If the answer is , then give it as .

**Input Format**

The first line of each test file contains a single integer , which is the number of queries per this file. lines follow with integers separated by single spaces on each: the corresponding , , and .

**Constraints**

**Output Format**

Print exactly lines with the answer for the corresponding query on each.

**Sample Input 0**

```
1
1 4 1 4
```

**Sample Output 0**

```
633077761
```

**Explanation 0**

There are combinations in total. Peter wins Colin in of them:

- Peter: , Colin:
- Peter: , Colin:
- Peter: , Colin:
- Peter: , Colin:
- Peter: , Colin:
- Peter: , Colin: