配点

満点

120

部分点

30

---

問題文

A君とT君とJさんは地下世界を走る列車のそれぞれの運行区間表を見ていた。Jさんがいくつかの運行区間をピラミッド型に並べられることに気づき、A君とT君に並べ方が何通りあるか調べるよう命令した。

いま$N$個の運行区間が与えられる。ここからちょうど$D$要素からなる運行区間列\[ A_1,A_2,...,A_D \]で、任意の$i=1,...,D-1$について$(A_iの始点)<(A_{i+1}の始点)$かつ$(A_{i+1}の終点)< (A_iの終点)$が常に成り立つようなものの個数を数える。相異なる運行区間列の個数を$314159265$で割った余りを求めよ。

---

入力形式

入力は以下の形式で与えられる。

$N\\ D\\\\ left_1\\ right_1\\\\ left_2\\ right_2\\\\ ...\\\\ left_N\\ right_N$

$N$は運行区間の個数を表す。 $left_i$は、$i$番目の運行区間の始点の位置、 $right_i$は、$i$番目の運行区間の終点の位置を表す。

出力形式

組合せを1行に出力せよ。

制約

• $2 ≤ N ≤ 100000$
• $2 ≤ D ≤ 15$
• $\-10^9 ≤ left_i,\\ right_i ≤ 10^9$
• $left_i < right_i$
• $left_i, right_j$はすべて相異なる。
• 入力値はすべて整数である。

この問題の判定には、$30$ 点分のテストケースのグループが設定されている。 このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす。

• $D=2$

---

入力例 1

3 2
1 7
2 4
8 10

出力例 1

1

図の通り、$1$番目の運行区間と$2$番目の運行区間からなる区間列のみが条件を満たす。

図1

---

入力例 2

5 4
1 10
2 9
3 8
4 7
5 6

出力例 2

5

$5$個からどの$4$個を選んでも並べ替えて条件を満たすようにできるので、$C(5,4)=5$通りとなる。

図2

---

入力例 3

4 2
1 10
2 5
3 4
8 11

出力例 3

3

---

入力例 4

4 3
1 7
2 8
3 6
4 5

出力例 4

2

---

Writer: uwi

---

Source Name

Autumn Fest

---