题目描述

给定一个 $n \times n$ 的网格地图，其中：

• . 表示可通行区域
• # 表示不可通行区域
  保证左上角 $(1,1)$ 和右下角 $(n,n)$ 一定可通行。

两人分别从不同起点出发：

• ​角色 A 从左上角 $(1,1)$ 出发，​只能向右或向下移动，目的地为右下角 $(n,n)$
• ​角色 B 从右下角 $(n,n)$ 出发，​只能向左或向上移动，目的地为左上角 $(1,1)$

求满足以下条件的路径方案数（对 $10^9+7$ 取模）：

1. 两人的路径均完全处于可通行区域
2. 两人的路径不存在任何交点​（包括路径上的点和边）

输入格式

• 第一行：整数 $n$，表示地图大小
• 第 $2$ 至 $n+1$ 行：每行 $n$ 个字符，表示地图

输出格式

• 单个整数，表示合法路径方案数 $\bmod 10^9+7$

数据范围

4
....
....
....
....

20

4
..##
...#
#...
##..

0