fork download
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define MOD 1000000007
  5. #define MAX_N 1200
  6.  
  7. int dp[MAX_N][MAX_N],p[MAX_N][MAX_N],h,w,k,x,y;
  8.  
  9. int main(){
  10. cin>>h>>w>>k;
  11. for(int i=0;i<k;i++){
  12. cin>>x>>y;
  13. p[x+2][1]++;
  14. p[x+2][y]--;
  15. p[1][y+2]++;
  16. p[x][y+2]--;
  17. }
  18. for(int i=1;i<=h;i++){
  19. for(int j=2;j<=w;j++){
  20. p[i][j]+=p[i][j-1];
  21. }
  22. }
  23. for(int i=1;i<=w;i++){
  24. for(int j=2;j<=h;j++){
  25. p[i][j]+=p[i-1][j];
  26. }
  27. }
  28. dp[1][1]=1;
  29. for(int i=1;i<=h;i++){
  30. for(int j=1;j<=w;j++){
  31. if(p[i][j]==0 && i+j>=3){
  32. dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;
  33. }
  34. }
  35. }
  36. cout<<dp[h][w]<<endl;
  37. return 0;
  38. }
Success #stdin #stdout 0s 14712KB
stdin
4 4 1
2 2
stdout
18