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)$ 点からちょうど二点を選び、幕の線の両端を支えます。
幕が邪魔されないよう、二柱間の張った線の真下に柱があってはいけません。
掛け方の数を求めてください。数は大きく 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