問題文

ここ数日で門松列に関する問題が頻出しております．
ここでは演習を通じて，門松列に対する理解を深め，門松列の問題が出題された時に解けるようになっておきましょう．
門松列対策講座を受講される皆様は既にご存知かと思いますが，門松列とは $3$ 個の要素からなる数列 $a,b,c$ で以下の $2$ つの条件を満たすものです．
・$a,b,c$ は全て異なる
・$3$ つの要素の中で $b$ が最も大きい，または，$b$ が最も小さい

この問題では通常の門松列ではなく，最近ブームになりつつあるスーパーリッチ門松列を考えましょう．
スーパーリッチ門松列とは $7$ 個の要素からなる数列 $a,b,c,d,e,f,g$ で以下の $2$ つの条件を満たすものです．
・$a,b,c,d,e,f,g$ は全て異なる
・$\min(b,d,f) > \max(a,c,e,g)$ または $\max(b,d,f) < \min(a,c,e,g)$
（直感的には，全要素異なり，偶数番目の要素が小さい方から3つ，または，大きい方から3つになっているということです．ジグジグザグザグ）

由岐さんは得体の知らないものをよく知るための第一歩は数えることだと思っています．
そこで，各要素 $x=a,b,c,d,e,f,g$ の下限 $x_{\min}$ と上限 $x_{\max}$ が与えられるので，$x_{\min} \leq x \leq x_{\max}$ を満たし，更に全ての要素が整数からなるスーパーリッチ門松列の数を数えるプログラムを書いてください．
ただし，答えは大きくなるかもしれないので答えを $10^9+7$ で割った余りを出力してください．

入力

$a_{\min}$ $a_{\max}$
$b_{\min}$ $b_{\max}$
$c_{\min}$ $c_{\max}$
$d_{\min}$ $d_{\max}$
$e_{\min}$ $e_{\max}$
$f_{\min}$ $f_{\max}$
$g_{\min}$ $g_{\max}$

$1 \leq x_{\min} \leq x_{\max} \leq 20000 = 2 \times 10^4$（$x=a,b,c,d,e,f,g$）

出力

条件を満たすスーパーリッチ門松列の数 ${\rm modulo}\ 10^9+7$ の値を出力してください．

サンプル

6 8
3 10
7 10
8 12
4 10
1 9
7 16

8

1 7
1 7
1 7
1 7
1 7
1 7
1 7

288

1 20000
1 20000
1 20000
1 20000
1 20000
1 20000
1 20000

96826092

2012 2019
2011 2017
2011 2018
2012 2019
2015 2015
2008 2018
2006 2019

2015