H - U・N・C・O Editorial /

Time Limit: 4 sec / Memory Limit: 128 MB

配点

満点
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