Welcome Home Banner

Farmer John wishes to hang a welcome home banner for Bessie on his rectangular field. The field has integer dimensions n by m, and a post is placed at every lattice point (i.e. every point with integer coordinates in the range [0, n] × [0, m]). John chooses two distinct posts A and B to hang the banner. However, because he insists that the banner be perfectly straight, the segment AB must not contain any other post (lattice point) apart from its endpoints.

Moreover, the length of the banner, i.e. the distance between A and B, must be at least l and at most h (inclusive). Since the banner is reversible, the order of endpoints does not matter. Because the answer can be very large, output the answer modulo B.

Note: A line segment between two lattice points (x₁,y₁) and (x₂,y₂) has no other lattice points on it if and only if the vector (x₂ − x₁, y₂ − y₁) is primitive (i.e. the greatest common divisor of its coordinates is 1). Also, the Euclidean distance between two points (x₁,y₁) and (x₂,y₂) is given by \(\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}\). All formulas in this problem are expressed in LaTeX format.

For example, consider the case where n = 2, m = 2, l = 1 and h = 3. The field looks like:

* * *
* * *
* * *

There are \(\binom{9}{2} = 36\) ways to choose two posts, but 8 of these choices yield a segment that contains an intermediate post. (For example, the segment joining (0,0) and (2,0) contains (1,0).) Hence the answer is 28.

inputFormat

The input consists of five integers separated by spaces:

• n and m: the dimensions of the field (0 ≤ x ≤ n, 0 ≤ y ≤ m). (1 ≤ n, m ≤ 100,000)
• l and h: the minimum and maximum allowable banner length (1 ≤ l ≤ h ≤ 150,000).
• B: the modulus (1 ≤ B ≤ 1,000,000,000).

You may assume the five numbers appear on one line.

outputFormat

Output a single integer: the number of valid unordered pairs of posts, modulo B.

sample

2 2 1 3 1000000007

28