\(2\) つ解法がありますが、いずれも多項式の積分をすることになります。多項式の \(ax+b\) 倍、微分、積分、\(x\) に代入して求められる値の計算などを mod \(10^9+7\) で出来るようにしておくと楽でした。

まず、確率変数がとりうる値の範囲を \(O(N)\) 個の区間に分けて、同じ区間の中では \(N\) 個の区間のそれぞれの内外関係が同じになるものをまとめて処理するとやりやすいです。これは入力で与えられる \(2N\) 個の値を全て \(1\) つにまとめてソートしておけば良いです。

以下、区間 \([P,Q)\) (上の処理で得られる区間) に対応する期待値(の断片)の求め方を説明します。これの総和をとって \((N+1)! \times (\)区間の長さの総積\()\) 倍すれば求める答えとなります (解法 \(2\) の場合はオフセットがずれるので事前に \(2N\) 個の値の最小値を足す必要があります) 。

解法 \(1\)

区間 \([P,Q)\) 内の値 \(x\) が最大値となる場合を考えます。\(max L ≤ Q\) が成り立たない場合、区間 \([P,Q)\) 内の値 \(x\) が最大値となることはありません。

その他の場合、全ての確率変数の値が \(x\) 以下となるのは、\(f(x) = \prod_{R_i ≥ P} \frac{x-L_i}{R_i-L_i}\) です。

\([x,x+dx)\) が最大となる確率は \(f(x+dx)-f(x)\) であるから、\(dx \rightarrow 0\) とすると、求める期待値は \(\int_P^Q xf'(x)dx\) となります。

解法 \(2\)

\(g(x) := (\) 最大値が \(x\) 以上となる確率 \()\) とすると、求める答えは \(\int_0^{+∞} g(x)dx\) です。(積分の始点に注意！)

\(x ≤ max L\) では、 \(g(x) = 1\) が常に成り立ちます。

そのほかの場合、\(g(x) = 1 - \prod_{R_i ≥ P} \frac{x-L_i}{R_i-L_i}\) です。