### 问题描述 对于一个长为 $n$ 的排列 $p$，根据排列 $p$ 建一个有 $n$ 个节点的无向图。对于每一对满足 $1 \le i < j \le n$ 的 $(i,j)$，如果 $p_i > p_j$，则在节点 $i,j$ 之间连一条无向边。 定义一个排列是好的，当且仅当依照上面的方式建图后得到的图为二分图。 现在有 $q$ 个限制，每个限制为要求排列前 $x$ 个数中最大的数为第 $k$ 个数，求有多少好的排列满足全部限制，答案对 $10^9+7$ 取模。 ### 输入格式 输入第一行包含两一个正整数 $n,q$，表示排列的长度和限制的个数。 接下来 $q$ 行，每行包含两个正整数 $x,k$，表示一个限制，要求排列前 $x$ 个数中最大的数为第 $k$ 个数。 ### 输出格式 一个整数，表示满足全部限制的好的排列的个数，答案对 $10^9 + 7$ 取模。 ### 样例输入 ```text 3 1 2 1 ``` ### 样例输出 ```text 2 ``` ### 说明 长为 $3$ 的排列共有 $6$ 个：$(1,2,3)$，$(1,2,3)$，$(2,1,3)$，$(2,3,1)$，$(3,1,2)$，$(3,2,1)$。 排列 $(1,2,3)$，$(1,2,3)$，$(2,3,1)$ 前两个数中最大的数均为第二个数，但根据要求，前两个数中最大的数应为第一个数，不符合要求。 排列 $(3,2,1)$ 虽然满足要求，但按照题目中的方式建图后，图中共有三条边 $(1,2)$，$(1,3)$，$(2,3)$，不为二分图。所以排列 $(3,2,1)$ 不是好的，也不符合要求。 综上，只有两个排列 $(2,1,3)$，$(3,1,2)$ 符合要求。 ### 评测数据规模 对于 $20$% 的评测数据，$1\leq n \leq 20$。 对于 $100$% 的评测数据，$1\leq n\leq 2000$，$0\leq q \leq n$，$1\leq k \leq x \leq n$。