Times Square

問題

$N$ 行 $N$ 列の表があります。この表の $i$ 行 $j$ 列 ($1 \leq i, j \leq N$) には、 $i$ と $j$ の積が書き込まれています。

以下、この表の $i$ 行 $j$ 列のことを $(i, j)$ と表します。

数 $a, b, c, d$ が与えられるので、この表において $4$ 点 $(a, b), (c, b), (a, d), (c, d)$ を頂点に持つ長方形内にある、全ての数字の和を求めてください。

なお、答えは非常に大きくなることがあるので、 $10^9 + 7$ で割った余りを求めてください。

制約

• $1 \leq N \leq 10^5$
• $1 \leq a \leq c \leq N$
• $1 \leq b \leq d \leq N$

入力

ひとつの入力に複数のテストケースが含まれ、ひとつのテストケースは以下のような形式で入力されます。

$N$
$a$ $b$ $c$ $d$

ひとつの入力に含まれるテストケースの総数は、最大 $30$ です。

$N$ は問題で扱う表の大きさ、$a, b, c, d$ は表の中の座標を示す定数です。

入力の終わりはひとつの $0$ からなる行で示されます。

出力

各テストケースについて、答えを $10^9 + 7$ で割った余りを求めてください。

ひとつのテストケースへの解答を出力するごとに、ひとつ改行してください。

入力例

9
3 4 5 5
100000
90000 90000 100000 100000
0

出力例

108
706236486

ひとつめの入力例では、表は下図のようになり、下図の黄色で示した箇所が和を求める領域となります。

したがって答えは $12+15+16+20+20+25 = 108$ となります。

---