题目描述

徐老师派机器人去参加一场躲避球大赛

这场比赛的规则是这样的，一共有 $n$ 个房间，一开始玩家会处于其中编号为 $x$ 的房间，一共进行 $m$ 轮挑战，任何一轮挑战失败即淘汰，全部通过的选手可以晋级决赛

每轮游戏开始前，玩家可以选择是否要移动到相邻编号的房间，例如第一轮游戏开始前可以选择是否要移动到 $x-1$ 或者 $x+1$ 房间，也可以选择不移动

当然玩家无法移动到不存在的房间，即 $0$ 和 $n + 1$

每轮游戏都会在每个房间内随机出现躲避球挑战，玩家需要在持续时间内完美躲避所有的球不被碰到才能获胜，但是众所周知，徐老师的机器人不具备转身功能，更不用说希望它去参加以灵活为核心的躲避球挑战了

于是徐老师仔细研究了游戏规则，发现游戏使用的随机数是伪随机

也就是每轮游戏中会存在一些房间不会出现躲避球挑战！

现在徐老师已经提前计算出了每轮游戏中有哪些房间不会出现躲避球挑战，那么只要每轮游戏机器人呆在这些房间内，就可以成功晋级下一轮

当然，由于机器人无法转身，只要它所在的房间出现了躲避球挑战，不论挑战难度简单与否，机器人都会失败

现在徐老师想知道，有多少种不同的移动方案可以使得机器人晋级到决赛？

这里徐老师认为，只要其中任何一轮的移动和之前的方案不同，那么就是一种不同的移动方案

输入格式

第一行一个整数 $n,m,x$ 含义如题

接下来 $m$ 行，每行两个整数 $l_i,r_i$ 表示第 $i$ 轮游戏中编号 $l \sim r$ 的这些房间是不会出现躲避球挑战的（包含 $l$ 和 $r$）

输出格式

输出共一行包含一个整数，表示不同的方案数，由于答案可能很大，请你将答案对 $10^9+7$ 取模后输出

数据范围

对于 $40\%$ 的数据保证 $1 \leq n,m \leq 10$

对于 $60\%$ 的数据保证 $1 \leq n \leq 100, 1 \leq m \leq 200$

对于 $100\%$ 的数据保证 $1 \leq n \leq 10000, 1 \leq m \leq 500$

对于所有数据保证 $1 \leq l_i \leq r_i \leq n$

样例输入1

3 3 1
2 2
1 3
2 3

样例输出1

5

样例说明1

游戏共三个房间，持续 $3$ 轮。初始在 $1$ 号房间 第一秒要求你在 $2$ 号房间中 第二秒要求你在 $1 \sim 3$ 号房间的任意一个 第三秒要求你在 $2 \sim 3$号房间的任意一个

一共有五种不同的移动方案

1. $1 \rightarrow 2 \rightarrow 1 \rightarrow 2$
2. $1 \rightarrow 2 \rightarrow 2 \rightarrow 2$
3. $1 \rightarrow 2 \rightarrow 2 \rightarrow 3$
4. $1 \rightarrow 2 \rightarrow 3 \rightarrow 2$
5. $1 \rightarrow 2 \rightarrow 3 \rightarrow 3$