from heapq import heappush, heappop, heapify import sys from collections import defaultdict, deque,Counter from math import ceil, floor, sqrt, factorial,gcd from itertools import permutations, combinations,product from bisect import bisect_left, bisect_right from copy import deepcopy from functools import lru_cache #@lru_cache(maxsize=None) from fractions import Fraction sys.setrecursionlimit(10**6) # input = sys.stdin.readline vector1 = [[0, -1], [1, 0], [0, 1], [-1, 0]] vector2 = [[0, 1], [1, 0], [-1, 0], [0, -1], [1,-1], [-1, 1], [1, 1], [-1, -1]] def main(): h,w = map(int,input().split()) a = [input() for i in range(h)] q = deque() q.append([0,0,1]) memo = defaultdict(int) md = defaultdict(lambda:-1) memo[(0,0)] = 1 md[(0,0)] = 0 ans = 0 while q: x,y,c = q.popleft() if x==h-1 and y==w-1: ans += 1 for dx,dy in vector1: nx = x+dx ny = y+dy if 0<=nx