解説AC
E - 通勤経路
制約のせいで場合分けが面倒．どこから来て，今どこへ曲れるかを考えて実装する．
w, h = map(int, input().split()) dp = [[[0]*4 for _ in range(w)] for _ in range(h)] for i in range(h): for j in range(w): if i == 0 and j == 0: continue if i == 0: dp[i][j][3] = 1 continue if j == 0: dp[i][j][0] = 1 continue dp[i][j][0] = (dp[i - 1][j][0] + dp[i - 1][j][1]) % 100000 dp[i][j][1] = dp[i - 1][j][3] % 100000 dp[i][j][2] = dp[i][j - 1][0] % 100000 dp[i][j][3] = (dp[i][j - 1][2] + dp[i][j - 1][3]) % 100000 print(sum(dp[-1][-1]) % 100000)
