Беси возвращается домой после длительного путешествия, а Фермер Джон хочет встретить ее баннером "Welcome Home". Поле ФД представляет собой целочисленную решетку размером M*N (1 <= M, N <= 100,000). Левый нижний угол поля имеет координаты (0,0), правый верхний - координаты (M,N). В каждой целочисленной точке поля вкопан столб. Из этих (M+1) * (N+1) точек ФД должен выбрать две в качестве конечных точек баннера.
Баннер должен быть точно прямым. Это означает, что на отрезке прямой между столбами, которые ФД выберет, не должно быть других столбов Кроме того, ФД хочет, чтобы баннер имел длину не менее L и не более H (1 <= L <= H <= 150,000).
Посчитайте, сколько существует различных способов повесить баннер. Способ, в котором меняются точки начала и конца друг с другом, считается одним и тем же. Поскольку число может быть очень большим, выводите ответ по модулю B (1 <= B <=1,000,000,000).
Рассмотрим пример M = 2 и N = 2:
* * * * * * * * *
ФД хочет баннер с длиной от 1 до 3 метров включительно. Все способы подходят по длине, но 8 пар должны быть исключены: Farmer John wants the length of the banner to be between 1 and 3 inclusive.
(0, 0) и (2, 0): (1, 0) на отрезке между ними (0, 1) и (2, 1): (1, 1) на отрезке между ними (0, 2) и (2, 2): (1, 2) на отрезке между ними (0, 0) и (2, 2): (1, 1) на отрезке между ними (0, 0) и (0, 2): (0, 1) на отрезке между ними (1, 0) и (1, 2): (1, 1) на отрезке между ними (2, 0) и (2, 2): (2, 1) на отрезке между ними (0, 2) и (2, 0): (1, 1) на отрезке между ними
Таким образом, ответ = (к-во способов из 9 по 2) - 8 = 28 вариантов.
PROBLEM NAME: banner
Формат входных данных
* Строка 1: Пять разделенных пробелом целых чисел: M, N, L, H, B.
Формат выходных данных
* Строка 1: Одно целое число, обозначающее количество баннеров по модулю B
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 1 3 100
|
28
|