Easy Brackets Problem

时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

For a number sequence $a$ of length $2n$ and a bracket sequence $s$ of $2n$ , denote that $f(a,s)=\sum\limits_{i=1}^{2n}a_i[s_i],$
where $[s_i]=\begin{cases}1,&s_i=\text{`}(\text{'},\\0,&s_i=\text{`})\text{'}\end{cases}.$

Randias is facing a too easy problem:

Given a number sequence $a$ of length $2n$ , find the value of $F(a)=\max \{f(a,s):$ where $s$ is a regular bracket sequence of $2n\}$ .

For example, $F(\{1,2,1,2\})=f(\{1,2,1,2\}$ ,"(())" $)=3$ and $F(\{1,2,3,4\})=f(\{1,2,3,4\}$ ,"()()" $)=4$ ,

Since this problem is too easy for Randias, so he's thinking of another easy problem:

For each $i=1$ , $2$ , $\dots$ , $2n$ , $a_{i}$ is a uniformly random real number picked from $[L_{i},R_{i}]$ , find the expected value of $F(a)$ .

He wants you to find the answer of the easy problem and output it modulo $10^9+7$ .

A bracket sequence is called regular if it is possible to obtain a correct arithmetic expression by inserting characters '+' and '1' into it. For example, sequences "(())()", "()", and "(()(()))" are regular, while ")(", "(()", and "(()))(" are not.

输入描述:

The first line contains one integer  (), representing the half of the length of the sequence.

The following  lines, each of them contain two integers  (), representing the interval where  is picked from.

输出描述:

One single integer, representing the answer, modulo .

More precisely, assume the reduced fraction of the answer is , you should output the minimum non-negative integer  such that . You may safely assume that such  always exists in all test cases.

示例1

输入

复制

1
2 4
3 6

输出

复制

说明

示例2

输入

复制

输出

复制

833333342

示例3

输入

复制

输出

复制

96825414

备注:

For the first example, note that the only regular bracket is "()", so the answer is the expected value of , which is .

For the second example, we can choose from "(())" or "()()", which means the answer is the expected value of , one can prove that it equals to .