Bessie wraca z długiej podróży zagranicznej, a Farmer John chce piękny transparent „Witaj w domu” na jej pastwisku. Wisi między słupami na drucie długości $L1$..$L2$ ($1 \le L1 \le L2; L1 \le L2 \le 1,500$).
Pastwisko ma $W \times H$ ($1 \le W \le 1,000; 1 \le H \le 1,000$), słup w każdym całkowitym punkcie. Wybiera dokładnie dwa z $(W + 1) * (H + 1)$ punktów na końce drutu transparentu.
Żaden słup nie może być bezpośrednio pod napiętym drutem między wybranymi, by nie przeszkadzać.
Policz sposoby. Jest ich dużo, 32-bitowa liczba całkowita może nie wystarczyć.
Przykład $W = 2$, $H = 1$:
* * *
* * *Rozmiar $2..3$; $(2+1) * (1+1) = 6$ punktów i $\binom{6}{2} = (6*5)/(2*1) = 15$ możliwych par:
| $(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)$ |
Tylko cztery mają długość $2..3$:
| Długość | Długość | ||
|---|---|---|---|
| $(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)$ i $(0,1)-(2,1)$ mają słup na linii między końcami, więc nie pasują.
Tylko dwie z 15 par pasują.
Wejście
- Wiersz 1: cztery całkowite $W$, $H$, $L1$, $L2$ oddzielone spacjami.
Wyjście
- Wiersz 1: liczba całkowita, liczba możliwych transparentów.
Przykład
Wejście 1
2 1 2 3
Wyjście 1
2
Autor zadania: Nathan Pinsker, 2010