记录编号	381343	评测结果	AAAAAAAAAAAAAAA
题目名称	牛跳房子	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.550 s
提交时间	2017-03-11 12:30:15	内存使用	9.16 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cctype>
#include <list>
using namespace std;
#define MOD 1000000007
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
  }
  inline int readint(){
    char c; int r;
    while(c = readc()){if(c >= '0' && c <= '9'){r = c^0x30;break;}}
    while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return r;
  }
  inline int read_string(char *str){
    int len = 1;char c;
    while(!isalpha(c = readc()));str[0] = c;
    while(isalpha(c = readc()))str[len++] = c;
    str[len] = 0;
    return len;
  }
};using IO::read_string; using IO::readint;
struct node{
  node *ls, *rs;
  int sum;
  node(){
    ls = rs = NULL; sum = 0;
  }
};
void insert(node *&x, int p, int d, int L, int R){
  if(!x)x = new node();
  x->sum = ((x->sum+d)%MOD+MOD)%MOD;
  if(L == R && R == p)return;
  int M = (L+R)>>1;
  if(p <= M)insert(x->ls, p, d, L, M);
  if(p > M)insert(x->rs, p, d, M+1, R);
}
int query(node *x, int l, int r, int L, int R){
  if(!x)return 0;
  if(l <= L && R <= r)return x->sum;
  int M = (L+R)>>1, ret = 0;
  if(l <= M)ret += query(x->ls, l, r, L, M);
  if(r > M)ret = ((ret+query(x->rs, l, r, M+1, R))%MOD+MOD)%MOD;
  return ret;
}
int field[751][751];
int f[751][751];
int pre[751][751];
node *root[751*751];
int main(){
  freopen("hopscotch.in", "r", stdin);
  freopen("hopscotch.out", "w", stdout);
  int n, m, c; n = readint(); m = readint(); c = readint();
  for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)
    field[i][j] = readint();
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      if(i == 1 && j == 1)f[i][j] = 1;
      else
      f[i][j] = ((pre[i-1][j-1]-query(root[field[i][j]], 1, j-1, 1, m))%MOD+MOD)%MOD;
    }
    for(int j = 1; j <= m; j++){
      pre[i][j] = (((pre[i][j-1]+pre[i-1][j])%MOD-pre[i-1][j-1])%MOD+MOD)%MOD;
      pre[i][j] = (pre[i][j]+f[i][j])%MOD;
      insert(root[field[i][j]], j, f[i][j], 1, m);
    }
  }
  printf("%d\n", f[n][m]);
  return 0;
}