题目描述

一个平面直角坐标系上，有 $n$ 个点，标号为 $1$ 到 $n$，其中第 $i$ 个点的坐标为 $(x_i,y_i)$。

求满足以下两个条件的点列 $\{p_i\}$ 的数目（假设 $\{p_i\}$ 的长度为 $m$）：

1. 对任意 $1 \leq i < j \leq m$，必有 $y_{p_i} > y_{p_j}$；
2. 对任意 $3 \leq i \leq m$，必有 $x_{p_{i-1}} < x_{p_{i-2}}$ 或者 $x_{p_{i-2}} < x_{p_i}<x_{p_{i-1}}$。

求满足条件的非空序列 $\{p_i\}$ 的数目，结果对一个整数 $q$ 取模。

输入格式

第一行是两个由空格隔开的整数：$n,q$。 第二行到第 $n+1$ 行，每行有两个整数。其中的第 $i$ 行的两个整数分别是 $x_i$ 和 $y_i$。

输出格式

包含一个整数，表示序列 $\{p_i\}$ 的数目对 $q$ 取模的结果。

样例输入

10 714066300
122043478 641033841
714066299 635034305
746657703 531637642
923809017 950414613
512044248 945746679
960702607 362415165
985369962 27838545
198374904 283457437
173667857 723287266
944359487 878474416

样例输出

90

数据规模与约定

没有写明数据规模与约定。

题目来源

版权所有者：李新野