<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

106. The equation

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


There is an equation ax + by + c = 0. Given a,b,c,x1,x2,y1,y2 you must determine, how many integer roots of this equation are satisfy to the following conditions : x1<=x<=x2,   y1<=y<=y2. Integer root of this equation is a pair of integer numbers (x,y).


Input

Input contains integer numbers a,b,c,x1,x2,y1,y2 delimited by spaces and line breaks. All numbers are not greater than 108 by absolute value.


Output

Write answer to the output.


Sample Input

1 1 -3
0 4
0 4
Sample Output

4

<|response|>
1. Abridged Problem Statement
Given integers a, b, c and two intervals [x1,x2] and [y1,y2], count the number of integer pairs (x,y) satisfying
  a·x + b·y + c = 0
and
  x1 ≤ x ≤ x2, y1 ≤ y ≤ y2.

2. Key Observations
• Move the constant to the right side: a·x + b·y = –c.
• If a = b = 0 the equation is just c = 0; if c = 0 every point of the rectangle qualifies, otherwise none.
• Otherwise the Diophantine equation a·x + b·y = –c has integer solutions iff g = gcd(a,b) divides –c.
• By the extended Euclidean algorithm one finds a particular solution (x0, y0).
• The general integer solution is
  x = x0 + (b/g)·t,
  y = y0 – (a/g)·t,   t ∈ ℤ.
• Imposing x1 ≤ x ≤ x2 and y1 ≤ y ≤ y2 gives two integer intervals for t. Their intersection length is the answer. This single parametric formulation also covers the cases where exactly one of a, b is zero.

3. Full Solution Approach
Step 1. Set c := –c. Optionally normalize signs so that b ≥ 0 (negate a, b, c together if b < 0).
Step 2. If a = 0 and b = 0: print (x2–x1+1)·(y2–y1+1) when c = 0, otherwise 0.
Step 3. Compute g and one solution (x0, y0) of a·x + b·y = g with the extended Euclidean algorithm. If g ∤ c, print 0.
Step 4. Scale: x0 *= c/g, y0 *= c/g. The full family is x = x0 + dx·t, y = y0 + dy·t with dx = b/g, dy = –a/g.
Step 5. For each variable, compute the smallest and largest t that keep it inside its interval, using sign-aware helpers (`first_in_range_k` / `last_in_range_k`) that handle positive and negative steps. A boundary check confirms the extreme values really lie inside the rectangle (guards the degenerate step cases).
Step 6. Normalize each [lo, hi] pair so lo ≤ hi, intersect the x-interval and y-interval of t, and the intersection size (or 0 if empty) is the answer.

4. C++ Implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream &operator>>(istream &in, vector<T> &a) {
    for(auto &x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int64_t extend_gcd(int64_t a, int64_t b, int64_t &x, int64_t &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int64_t x1, y1;
    int64_t d = extend_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

int64_t a, b, c;
pair<int64_t, int64_t> range_x, range_y;

void read() {
    cin >> a >> b >> c;
    cin >> range_x >> range_y;
}

int64_t first_in_range_k(
    pair<int64_t, int64_t> range, int64_t x, int64_t delta
) {
    if(delta > 0) {
        if(x < range.first) {
            int64_t k = (range.first - x + delta - 1) / delta;
            return k;
        } else {
            int64_t k = (x - range.first) / delta;
            return -k;
        }
    } else {
        if(x >= range.first) {
            int64_t k = (x - range.first) / (-delta);
            return k;
        } else {
            int64_t k = (range.first - x - delta - 1) / (-delta);
            return -k;
        }
    }
}

int64_t last_in_range_k(
    pair<int64_t, int64_t> range, int64_t x, int64_t delta
) {
    if(delta > 0) {
        if(x > range.second) {
            int64_t k = (x - range.second + delta - 1) / delta;
            return -k;
        } else {
            int64_t k = (range.second - x) / delta;
            return k;
        }
    } else {
        if(x <= range.second) {
            int64_t k = (range.second - x) / (-delta);
            return -k;
        } else {
            int64_t k = (x - range.second - delta - 1) / (-delta);
            return k;
        }
    }
}

bool not_in_range(int64_t x, pair<int64_t, int64_t> range) {
    return x < range.first || x > range.second;
}

void solve() {
    c *= -1;

    if(b < 0) {
        a *= -1;
        b *= -1;
        c *= -1;
    }

    if(a == 0 && b == 0) {
        if(c == 0) {
            cout << (range_x.second - range_x.first + 1) * 1ll *
                        (range_y.second - range_y.first + 1)
                 << '\n';
        } else {
            cout << 0 << '\n';
        }
        return;
    }

    int64_t x, y;
    // a x + b y = g
    int64_t g = extend_gcd(a, b, x, y);

    if(c % g) {
        cout << 0 << '\n';
        return;
    }

    x *= c / g;
    y *= c / g;

    int64_t delta_x = b / g;
    int64_t delta_y = -a / g;

    int64_t lxk = first_in_range_k(range_x, x, delta_x),
            rxk = last_in_range_k(range_x, x, delta_x);
    int64_t lyk = first_in_range_k(range_y, y, delta_y),
            ryk = last_in_range_k(range_y, y, delta_y);

    if(not_in_range(x + lxk * delta_x, range_x) ||
       not_in_range(y + lyk * delta_y, range_y) ||
       not_in_range(x + rxk * delta_x, range_x) ||
       not_in_range(y + ryk * delta_y, range_y)) {
        cout << 0 << '\n';
        return;
    }

    if(lxk > rxk) {
        swap(lxk, rxk);
    }
    if(lyk > ryk) {
        swap(lyk, ryk);
    }

    int64_t ans = max(0ll, min(rxk, ryk) - max(lxk, lyk) + 1);
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments
```python
import sys
sys.setrecursionlimit(10**7)

# Extended GCD: returns (g, x, y) with a*x + b*y = g
def ext_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = ext_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return (g, x, y)

# smallest integer k with x + k*delta >= l (sign-aware)
def first_k(l, x, delta):
    if delta > 0:
        if x < l:
            return (l - x + delta - 1) // delta
        else:
            return -((x - l) // delta)
    else:
        if x >= l:
            return (x - l) // (-delta)
        else:
            return -((l - x + (-delta) - 1) // (-delta))

# largest integer k with x + k*delta <= r (sign-aware)
def last_k(r, x, delta):
    if delta > 0:
        if x > r:
            return -((x - r + delta - 1) // delta)
        else:
            return (r - x) // delta
    else:
        if x <= r:
            return -((r - x) // (-delta))
        else:
            return (x - r + (-delta) - 1) // (-delta)

def main():
    data = list(map(int, sys.stdin.read().split()))
    a, b, c = data[0], data[1], data[2]
    x1, x2, y1, y2 = data[3], data[4], data[5], data[6]

    # Move constant term: a*x + b*y = -c
    c = -c

    # Normalize so b >= 0
    if b < 0:
        a, b, c = -a, -b, -c

    # Case a=b=0
    if a == 0 and b == 0:
        print((x2 - x1 + 1) * (y2 - y1 + 1) if c == 0 else 0)
        return

    # Find g and a solution to a*x + b*y = g
    g, x0, y0 = ext_gcd(abs(a), abs(b))
    if a < 0: x0 = -x0
    if b < 0: y0 = -y0

    if c % g != 0:
        print(0)
        return

    # Scale solution to match a*x + b*y = c
    x0 *= c // g
    y0 *= c // g

    # Parameterize: x = x0 + (b/g)*t, y = y0 - (a/g)*t
    dx = b // g
    dy = -a // g

    lx, rx = first_k(x1, x0, dx), last_k(x2, x0, dx)
    ly, ry = first_k(y1, y0, dy), last_k(y2, y0, dy)

    def in_range(v, lo, hi):
        return lo <= v <= hi

    if not in_range(x0 + lx*dx, x1, x2) or not in_range(x0 + rx*dx, x1, x2) \
       or not in_range(y0 + ly*dy, y1, y2) or not in_range(y0 + ry*dy, y1, y2):
        print(0)
        return

    if lx > rx: lx, rx = rx, lx
    if ly > ry: ly, ry = ry, ly

    print(max(0, min(rx, ry) - max(lx, ly) + 1))

if __name__ == "__main__":
    main()
```
