gistfile1.c

#include <stdio.h>

#define UPPER 0
#define RIGHT 1

#define YES 0
#define NO 1

int main(){
  int m,n;

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

  int dp[m][n][2][2];
  int i,j;
  for(i=0;i<m;i++)
    for(j=0;j<n;j++){
      if(i==0) dp[i][j][RIGHT][YES] = 0,dp[i][j][RIGHT][NO] = 1;
      else if(j==0) dp[i][j][UPPER][YES] = 0,dp[i][j][UPPER][NO] = 1;
    }

  for(i=1;i<m;i++)
    for(j=1;j<n;j++){
      dp[i][j][UPPER][YES] = (dp[i][j-1][UPPER][YES] + dp[i][j-1][UPPER][NO])%100000;
      dp[i][j][UPPER][NO] = dp[i-1][j][RIGHT][YES];
      dp[i][j][RIGHT][YES] = (dp[i-1][j][RIGHT][YES] + dp[i-1][j][RIGHT][NO])%100000;
      dp[i][j][RIGHT][NO] = dp[i][j-1][UPPER][YES];
    }

  int answer = (dp[m-2][n-1][RIGHT][YES]+dp[m-2][n-1][RIGHT][NO]+dp[m-1][n-2][UPPER][YES]+dp[m-1][n-2][UPPER][NO])%100000;

  printf("%d\n", answer);
}