Description：

一个 $R\times C$ 的网格，每个格子有一个 $[1,k]$ 之间的标号，从左上角往右下角跳，要求格子行数列数严格增加且标号不同，求有多少种方案。

$1\leqslant R,C\leqslant 750$

Solution：

写一个暴力 $DP$ 式的话会发现是一个二维偏序 $+$ 一维限制的转移，可以 $CDQ$ 分治，但很棘手的是同一行和列之间不能相互转移，所以如果两个 $y$ 相同在左边的要后转移，并且 $x$ 要一块一块转移，也就是说不能把 $x$ 相同的分开。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MOD 1000000007

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

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

		c = getchar();

	}

	return res * f;

}

int n,m,k;

#define MAXN 751

int num[MAXN][MAXN];

int c[MAXN * MAXN];

struct query

{

	int x,y;

	bool operator < (query b)const

	{

		return x < b.x;

	}

}s[MAXN * MAXN];

int tot = 0;

int f[MAXN][MAXN];

bool cmp_x(query a,query b){return (a.x != b.x ? a.x < b.x : a.y < b.y);}

bool cmp_y(query a,query b){return a.y < b.y;}

inline void add(int &x,int y){x = (x + y % MOD) % MOD;return;}

void solve(int l,int r)

{

	if(s[l].x == s[r].x)return;

	register int mid = ((l + r) >> 1);

	mid = upper_bound(s + l,s + r + 1,(query){s[mid].x,0}) - s - 1;

	solve(l,mid);

	register int i = l,j = mid + 1;

	register int sum = 0;

	sort(s + l,s + mid + 1,cmp_y);

	sort(s + mid + 1,s + r + 1,cmp_y);

	for(;i <= mid && j <= r;)

	{

		if(s[i].y < s[j].y)

		{

			add(sum,f[s[i].x][s[i].y]);

			add(c[num[s[i].x][s[i].y]],f[s[i].x][s[i].y]);

			++i;

		}

		else

		{

			add(f[s[j].x][s[j].y],sum - c[num[s[j].x][s[j].y]] + MOD);

			++j;

		}

	}

	for(;j <= r;++j)add(f[s[j].x][s[j].y],sum - c[num[s[j].x][s[j].y]] + MOD);

	for(i -= 1;i >= l;--i)add(c[num[s[i].x][s[i].y]],-f[s[i].x][s[i].y] + MOD);

	sort(s + l,s + r + 1,cmp_x);

	solve(mid + 1,r);

	return;

}

int main()

{

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

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

		for(int j = 1;j <= m;++j)

			num[i][j] = read();

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

		for(int j = 1;j <= m;++j)

			s[++tot] = (query){i,j};

	f[1][1] = 1;

	sort(s + 1,s + 1 + tot,cmp_x);

	solve(1,tot);

	printf("%d\n",f[n][m]);

	return 0;

}