题目描述

Hitster 是一款通过猜测歌曲发行年份，将歌曲卡牌插入时间线的桌游。Harper 正在游玩它的单人版本。

游戏开始时，Harper 的时间线为空。每一轮中，她抽取一张卡牌：

1. 卡牌正面只有一个二维码，Harper 扫描后听到歌曲；
2. Harper 猜测这首歌的发行年份；
3. 随后翻开卡牌，得知歌曲的真实发行年份。

设真实年份为 $a$，Harper 猜测的年份为 $b$。

如果当前时间线中不存在真实发行年份严格位于 $a$ 与 $b$ 之间的歌曲，那么 Harper 将这张卡牌加入时间线；否则，她丢弃这张卡牌。

Harper 刚刚用完整的 $n$ 张牌进行了一次漫长的游戏。她记住了每首歌的真实年份以及自己当时的猜测，因此再次游玩时会对每张牌作出与上次相同的猜测。

现在，将这 $n$ 张牌按照所有 $n!$ 种排列中的一个等概率随机顺序依次呈现。请计算游戏结束时 Harper 时间线长度的期望值。

图 H.1：第三组样例按输入顺序呈现时的游戏过程。底部为 Harper 当前的时间线。第三轮结束后，时间线中共有两张卡牌。每轮上方右侧显示卡牌背面，即 Harper 作出猜测前无法看到的信息。

输入格式

第一行包含一个整数 $n$（$1\le n\le 3000$），表示卡牌数量。

接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i,b_i$（$1\le a_i,b_i\le 10^9$），分别表示第 $i$ 首歌的真实发行年份和 Harper 对它的猜测年份。

保证对于任意 $i\ne j$，均有：

因此，某张卡牌的猜测年份不会等于另一张卡牌的真实年份，卡牌在时间线中的位置总是唯一确定的。

输出格式

设模数

期望值可以写成既约分数 $\dfrac pq$，并且 $q$ 不被 $M$ 整除。

输出一个整数

即唯一满足 $0\le x<M$ 且

的整数 $x$。

样例 1

输入

2
2002 2004
2001 2003

输出

499122178

说明

共有两种呈现顺序：

• 若按输入顺序呈现，第一张牌加入时间线，第二张牌被丢弃；
• 若按相反顺序呈现，两张牌都会加入时间线。

因此期望长度为 $\dfrac32$。可以验证：

样例 2

输入

2
2001 2001
2002 2002

输出

2

样例 3

输入

3
1999 2003
1987 2005
2002 2001

输出

831870296