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 .