Bessie возвращается из долгой зарубежной поездки, и Farmer John хочет красивое знамя «С возвращением домой» на её пастбище. Знамя висит между двумя столбами на проволоке длиной $L1$..$L2$ ($1 \le L1 \le L2; L1 \le L2 \le 1,500$).
Пастбище $W \times H$ ($1 \le W \le 1,000; 1 \le H \le 1,000$), столб в каждой целой точке. Из $(W + 1) * (H + 1)$ точек надо выбрать ровно две для концов проволоки, держащей знамя.
FJ не хочет помех: прямо под натянутой между выбранными столбами проволокой не должно быть столба.
Найдите число способов. Оно велико, 32-битного целого может не хватить.
Пример при $W = 2$, $H = 1$:
* * *
* * *Размер знамени $2..3$. Есть $(2+1) * (1+1) = 6$ точек и $\binom{6}{2} = (6*5)/(2*1) = 15$ возможных пар для проволоки:
| $(0,0)-(0,1)$ | $(0,0)-(2,1)$ | $(0,1)-(2,1)$ | $(1,1)-(2,0)$ |
| $(0,0)-(1,0)$ | $(0,1)-(1,0)$ | $(1,0)-(1,1)$ | $(1,1)-(2,1)$ |
| $(0,0)-(1,1)$ | $(0,1)-(1,1)$ | $(1,0)-(2,0)$ | $(2,0)-(2,1)$ |
| $(0,0)-(2,0)$ | $(0,1)-(2,0)$ | $(1,0)-(2,1)$ |
Только четыре имеют длину $2..3$:
| Длина | Длина | ||
|---|---|---|---|
| $(0,0)-(2,0)$ | $2.00$ | $(0,1)-(2,0)$ | $2.24$ |
| $(0,0)-(2,1)$ | $2.24$ | $(0,1)-(2,1)$ | $2.00$ |
Пары $(0,0)-(2,0)$ и $(0,1)-(2,1)$ имеют столб на линии между концами и не подходят.
Из 15 пар подходят лишь две.
Входные данные
- Строка 1: четыре целых $W$, $H$, $L1$, $L2$ через пробел.
Выходные данные
- Строка 1: целое, число возможных знамён.
Примеры
Входные данные 1
2 1 2 3
Выходные данные 1
2
Автор задачи: Nathan Pinsker, 2010