AT_dp_h Grid 1

[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_h 縦 $ H $ 行、横 $ W $ 列のグリッドがあります。 上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,\ j) $ で表します。 各 $ i,\ j $ ($ 1\ \leq\ i\ \leq\ H $, $ 1\ \leq\ j\ \leq\ W $) について、マス $ (i,\ j) $ の情報が文字 $ a_{i,\ j} $ によって与えられます。 $ a_{i,\ j} $ が `.` ならばマス $ (i,\ j) $ は空マスであり、$ a_{i,\ j} $ が `#` ならばマス $ (i,\ j) $ は壁のマスです。 マス $ (1,\ 1) $ および $ (H,\ W) $ は空マスであることが保証されています。 太郎君は、マス $ (1,\ 1) $ から出発し、右または下に隣り合う空マスへの移動を繰り返すことで、マス $ (H,\ W) $ まで辿り着こうとしています。 マス $ (1,\ 1) $ から $ (H,\ W) $ までの太郎君の経路は何通りでしょうか？ 答えは非常に大きくなりうるので、$ 10^9\ +\ 7 $ で割った余りを求めてください。

N/A

N/A

### 制約 - $ H $ および $ W $ は整数である。 - $ 2\ \leq\ H,\ W\ \leq\ 1000 $ - $ a_{i,\ j} $ は `.` または `#` である。 - マス $ (1,\ 1) $ および $ (H,\ W) $ は空マスである。 ### Sample Explanation 1 経路は次図の $ 3 $ 通りです。 !\[\](https://img.atcoder.jp/dp/grid\_0\_0\_muffet.png) ### Sample Explanation 2 経路が存在しない場合もあります。 ### Sample Explanation 4 答えを $ 10^9\ +\ 7 $ で割った余りを出力することを忘れずに。