- All Contests
- ProjectEuler+
- Project Euler #198: Ambiguous Numbers

# Project Euler #198: Ambiguous Numbers

# Project Euler #198: Ambiguous Numbers

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

A best approximation to a real number for the denominator bound is a rational number (in reduced form) with , so that any rational number which is closer to than has .

Usually the best approximation to a real number is uniquely determined for all denominator bounds. However, there are some exceptions, e.g. has the two best approximations and for the denominator bound . We shall call a real number *ambiguous*, if there is at least one denominator bound for which possesses two best approximations. Clearly, an ambiguous number is necessarily rational.

How many ambiguous numbers ,, are there whose denominator does not exceed ?

**Input Format**

The only line of each test case contains exactly five space-separated integers: ,,,and.

**Constraints**

- ,
- ,

**Output Format**

On a single line print the answer modulo .

**Sample Input 0**

```
1 4 1 2 25
```

**Sample Output 0**

```
3
```

**Explanation 0**

There are rational numbers between and with the denominator no greater than :

, , , , , , , , , ,

, , , , , , , , , ,

, , , , , , , , , ,

, , , , , , , , , ,

, , , , , , , and .

Only three of them are *ambiguous* numbers: , and

- and are the two best approximations of for the denominator bound ;
- and are the two best approximations of for the denominator bound ;
- and are the two best approximations of for the denominator bound .

Therefore the answer is .