有 n 个随机变量 x[1],x[2],...,x[n] ，其中 x[i] 是l[i] 到 r[i] 之间的随机的一个整数。这 n 个随机变量的值会有一共 (r[1]-l[1]+1)*(r[2]-l[2]+1)*...*(r[n]-l[n]+1) 种情况。

对于某种情况，令 h=max{x[1],x[2],...,x[n]}，定义这种情况的权值为：(h-x[1]+1)*(h-x[2]+1)*...*(h-x[n]+1) 。

请问权值的期望是多少？请将答案对 10^9+7 取模后输出。

第一行一个整数 n 。
接下来 n 行，每行两个数，表示 l[i]和 r[i] 。

一行，一个整数，表示答案。假设答案为 p/q，请输出p×q^(−1) mod 10^9 +7，此处 q^(−1) 为 q 的逆元。

3
2 5
2 4
2 5

875000012

共 10 个测试点。
测试点 1,2 满足 n≤5, r[i] ≤ 10。
测试点 3,4,5,6 满足 n ≤ 100, r[i] ≤ 100。
对于所有数据，满足 1 ≤ n ≤ 1000,1 ≤ l[i] ≤ r[i]≤ 10^4。