AT_abc183_e [ABC183E] Queen on Grid

[problemUrl]: https://atcoder.jp/contests/abc183/tasks/abc183_e 縦 $ H $ マス、横 $ W $ マスのグリッドがあります。 上から $ i $ 行目、左から $ j $ 列目のマス $ (i,j) $ は、$ S_{ij} $ が `#` のとき壁であり、`.` のとき道です。 マス $ (1,1) $ にチェスのクイーンの駒が置いてあります。 クイーンの駒は、今いる位置から右・下・右下方向に伸びる直線上にあり、壁を飛び越えずに到達できる道のマスに $ 1 $ 手で移動することができます。 クイーンの駒がマス $ (1,1) $ からマス $ (H,W) $ まで移動する方法は何通りありますか？ $ \bmod\ (10^9+7) $ で求めてください。 ただし、移動する方法が異なるとは、ある $ i $ が存在して、$ i $ 手目の移動の後にクイーンの駒があるマスの位置が異なることを指します。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_{11}\ldots\ S_{1W} $ $ \vdots $ $ S_{H1}\ldots\ S_{HW} $

クイーンの駒がマス $ (1,1) $ から $ (H,W) $ まで移動する方法の数を $ \mod\ (10^9+7) $ で出力せよ。

### 制約 - $ 2\ \leq\ H,W\ \leq\ 2000 $ - $ S_{ij} $ は `#` か `.` - $ S_{11} $ と $ S_{HW} $ は `.` ### Sample Explanation 1 移動方法として次の $ 10 $ 通りが考えられます。 - $ (1,1)\to\ (1,2)\to\ (1,3)\to\ (2,3)\to\ (3,3) $ - $ (1,1)\to\ (1,2)\to\ (1,3)\to\ (3,3) $ - $ (1,1)\to\ (1,2)\to\ (2,3)\to\ (3,3) $ - $ (1,1)\to\ (1,3)\to\ (2,3)\to\ (3,3) $ - $ (1,1)\to\ (1,3)\to\ (3,3) $ - $ (1,1)\to\ (2,1)\to\ (3,1)\to\ (3,2)\to\ (3,3) $ - $ (1,1)\to\ (2,1)\to\ (3,1)\to\ (3,3) $ - $ (1,1)\to\ (2,1)\to\ (3,2)\to\ (3,3) $ - $ (1,1)\to\ (3,1)\to\ (3,2)\to\ (3,3) $ - $ (1,1)\to\ (3,1)\to\ (3,3) $ ### Sample Explanation 2 $ (1,1) $ からは $ 1 $ 手で $ (1,2),(1,3),(2,1),(2,2),(3,1),(4,1) $ のいずれかへ移動することが出来ます。 $ (4,4) $ への移動経路として、例えば $ (1,1)\to\ (3,1)\to\ (3,2)\to\ (4,3)\to\ (4,4) $ などがあります。 ### Sample Explanation 3 移動方法の数を $ \bmod\ (10^9+7) $ で求めてください。