链接: https://cses.fi/problemset/task/1638

板块: Dynamic Programming

时限: 1.00 s ｜ 内存: 512 MB

题目描述

考虑一个 $n \times n$ 的网格，其中某些格子可能有陷阱。不允许移动到有陷阱的格子。

你的任务是计算从左上角格子到右下角格子的路径数量。你只能向右或向下移动。

输入

第一行输入包含一个整数 $n$：网格的大小。

之后有 $n$ 行描述网格。每行包含 $n$ 个字符：. 表示空格子，* 表示陷阱。

输出

输出路径数量对 $10^9+7$ 取模的结果。

数据范围

$1 \le n \le 1000$

样例输入

4
....
.*..
...*
*...

样例输出

3