Grid Paths I

题目描述

考虑一个 n \times n 的网格，网格中的方格可能有陷阱。不能移动到有陷阱的方格。 你的任务是计算从左上角方格到右下角方格的路径数。你只能向右或向下移动。

输入格式

第一行输入是一个整数 n：网格的大小。 随后有 n 行描述网格。每行有 n 个字符：. 表示空格子，* 表示陷阱。

输出格式

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

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

3

提示

$1 \le n \le 1000$

标签: CSES1638|动态规划|DP

来源

CSES1638|动态规划|DP