题目描述

考虑一个大小为 $n \times n$ 的网格，网格中的某些格子可能包含陷阱。不能移动到包含陷阱的格子。

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

输入格式

第一行是一个整数 $n$，表示网格的大小。

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

输出格式

输出一个整数，表示从左上角到右下角的路径数量，结果对 $10^9 + 7$ 取模。

样例

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

3

数据范围

• $1 \le n \le 1000$