Description

二维平面上有n个点(xi, yi)，现在这些点中取若干点构成一个集合S，对它们按照x坐标排序，顺次连接，将会构成一些连续上升、下降的折线，设其数量为f(S)。如下图中，1->2,2->3,3->5,5->6（数字为下图中从左到右的点编号），将折线分为了4部分，每部分连续上升、下降。

现给定k，求满足f(S) = k的S集合个数。

Input

第一行两个整数n和k，以下n行每行两个数(xi, yi)表示第i个点的坐标。所有点的坐标值都在[1, 100000]内，且不存在两个点，x坐标值相等或y坐标值相等

Output

输出满足要求的方案总数 mod 100007的结果

Sample Input

5 1

5 5

3 2

4 4

2 3

1 1

Sample Output

19

HINT

对于100%的数据，n <= 50000，0 < k <= 10

---

思路

首先把所有点按照x坐标排序

然后先考虑暴力DP

\(dp_{i,j,0}\)表示前i个点有j个折线数量，当前向上/下的方案数

然后发现每次查询是一个二维前缀和的东西

一维可以直接在原数组上累加

然后另一维树状数组做掉

---

//Author: dream_maker

#include<bits/stdc++.h>

using namespace std;

//----------------------------------------------

//typename

typedef long long ll;

//convenient for

#define fu(a, b, c) for (int a = b; a <= c; ++a)

#define fd(a, b, c) for (int a = b; a >= c; --a)

#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)

//inf of different typename

const int INF_of_int = 1e9;

const ll INF_of_ll = 1e18;

//fast read and write

template <typename T>

void Read(T &x) {

  bool w = 1;x = 0;

  char c = getchar();

  while (!isdigit(c) && c != '-') c = getchar();

  if (c == '-') w = 0, c = getchar();

  while (isdigit(c)) {

    x = (x<<1) + (x<<3) + c -'0';

    c = getchar();

  }

  if (!w) x = -x;

}

template <typename T>

void Write(T x) {

  if (x < 0) {

    putchar('-');

    x = -x;

  }

  if (x > 9) Write(x / 10);

  putchar(x % 10 + '0');

}

//----------------------------------------------

const int N = 1e5 + 10;

const int K = 20;

const int Mod = 1e5 + 7;

int n, k, maxy = 0;

int add(int a, int b) {

  return (a += b) >= Mod ? a - Mod : a;

}

int sub(int a, int b) {

  return (a -= b) < 0 ? a + Mod : a;

}

struct BIT{

  int t[N];

  BIT() {memset(t, 0, sizeof(t));}

  void modify(int x, int vl) {

    for (; x <= maxy; x += x & (-x))

      t[x] = add(t[x], vl);

  }

  int query(int x) {

    int res = 0;

    for (; x; x -= x & (-x))

      res = add(res, t[x]);

    return res;

  }

  int query(int l, int r) {

    return sub(query(r), query(l - 1));

  }

} bit[K][2];

struct Node {

  int x, y;

} p[N];

bool cmp(Node a, Node b) {

  return a.x < b.x;

}

int main() {

  Read(n); Read(k);

  fu(i, 1, n) {

    Read(p[i].x), Read(p[i].y);

    maxy = max(maxy, p[i].y);

  }

  sort(p + 1, p + n + 1, cmp);

  fu(i, 1, n) {

    bit[0][0].modify(p[i].y, 1);

    bit[0][1].modify(p[i].y, 1);

    fu(j, 1, k) {

      bit[j][0].modify(p[i].y, bit[j - 1][1].query(1, p[i].y - 1));

      bit[j][0].modify(p[i].y, bit[j][0].query(1, p[i].y - 1));

      bit[j][1].modify(p[i].y, bit[j - 1][0].query(p[i].y + 1, maxy));

      bit[j][1].modify(p[i].y, bit[j][1].query(p[i].y + 1, maxy));

    }

  }

  Write(add(bit[k][0].query(1, maxy), bit[k][1].query(1, maxy)));

  return 0;

}