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

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

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

5 1
5 5
3 2
4 4
2 3
1 1

19

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #define M 100010

 #define mod 100007

 using namespace std;

 struct point{int x,y;}a[M];

 bool cmp1(point a1,point a2) {return a1.x<a2.x;}

 bool cmp2(point a1,point a2) {return a1.y<a2.y;}

 int ans,n,m;

 int f[M][][];

 struct change_query

 {

     int val[M];

     void insert(int loc,int v)

     {

         for(int i=loc;i<=n;i+=i&(-i))

             (val[i]+=v)%=mod;

     }

     int query(int loc)

     {

         int ans=;

         for(int i=loc;i>;i-=i&(-i)) (ans+=val[i])%=mod;

         return ans;

     }

     int get(int l,int r) {return (query(r)-query(l-)+mod)%mod;}

 }T[][];

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);

     sort(a+,a++n,cmp2);

     for(int i=;i<=n;i++) a[i].y=i;

     sort(a+,a++n,cmp1);

     for(int i=;i<=n;i++)

     {

         f[i][][]=f[i][][]=;

         T[][].insert(a[i].y,f[i][][]);

         T[][].insert(a[i].y,f[i][][]);

         for(int k=;k<=m;k++)

         {

             int y=a[i].y;

             if(y!=)

             {

                 (f[i][k][]+=T[k][].get(,y-)+T[k-][].get(,y-))%=mod;//f[i][k][1]+=f[j][k][1]+f[j][k-1][0];

                 T[k][].insert(y,f[i][k][]);

             }

             if(y!=n)

             {

                 (f[i][k][]+=T[k][].get(y+,n)+T[k-][].get(y+,n))%=mod;//f[i][k][0]+=f[j][k][0]+f[j][k-1][1];

                 T[k][].insert(y,f[i][k][]);

             }

         }

     }

     for(int i=;i<=n;i++) (ans+=f[i][m][]+f[i][m][])%=mod;

     printf("%d",ans);

     return ;

 }