送到客人手上有幾條路

題目敘述

外送平台想評估一個街區的路線彈性。這個街區是一個方格狀的路網：店家在最西北角的路口，客人在最東南角的路口。由於單行道，外送員每一步只能往南或往東走，不能往北或往西。

有些路口因為施工完全不能通過。被封閉的路口可能剛好就是店家或客人所在的那一個，這種情況當然送不到。請計算從西北角走到東南角、且不經過任何封閉路口的路線有幾條。

輸入格式

第一行是兩個整數 R 與 C，表示路口共有 R 列、C 行。接下來 R 行，每行 C 個字元：. 表示可通行，# 表示封閉。

輸出格式

輸出一行：可行的路線數。

限制

• 1 <= R, C <= 20

範例

範例 1

輸入

3 3
...
.#.
...

輸出

2

說明

範例是 3 x 3 的路網，正中間封閉，所以只剩沿著邊緣走的兩條路線。