Number of solutions

Time limit1sMemory limit256 MB

Summary

Count the integer pairs (x, y) inside the given x and y ranges that satisfy Ax + By + C = 0.

Level: Medium5 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

Write a program that counts the integer solutions of the equation $Ax + By + C = 0$ .

$A$ , $B$ , $C$ , $x$ , and $y$ are all integers. Count the integer pairs $(x, y)$ that satisfy the equation with $x_1 \le x \le x_2$ and $y_1 \le y \le y_2$ .

If $A$ , $B$ , and $C$ are all $0$ , every integer pair inside the given ranges is a solution.

Input

The first line contains $A$ , $B$ , $C$ , $x_1$ , $x_2$ , $y_1$ , $y_2$ , separated by spaces. Every value is an integer between $-10^8$ and $10^8$ , and $x_1 \le x_2$ , $y_1 \le y_2$ .

Output

Print the number of solutions on the first line. The count can exceed the range of a 32-bit integer.

Examples4

Example 1
Input
```
1 1 1 -20 20 -30 30
```
Expected output
```
41
```
Example 2
Input
```
20 30 40 50 60 70 80
```
Expected output
```
0
```
Example 3
Input
```
-100 20 300 -100 200 -2000 3000
```
Expected output
```
301
```
Example 4
Input
```
-10 8 4 -100 100 -200 300
```
Expected output
```
50
```