题目描述

给定一个由 $n\times n$ 个方格组成的地图，. 表示可以通行，# 表示不可通行。保证左上角与右下角一定可以通行。

有一个人从左上角出发，只能向下或向右走，目的地是右下角。另一个人从右下角出发，只能朝上或朝左走，目的地左上角。请问有多少种不同的行走路线，可以让两人在地图上的路径没有交叉？

由于方案数很大，输出答案模 $1,000,000,007$ 的余数。

输入格式

• 第一行：单个整数表示 $n$
• 第二行到第 $n$ 行：每行 $n$ 个字符表示一行的地形。

输出格式

• 单个整数：表示答案。

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

20

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

0

数据范围

• 对于 $30\%$ 的数据，$2\leq n\leq 20$
• 对于 $60\%$ 的数据，$2\leq n\leq 200$
• 对于 $100\%$ 的数据，$2\leq n\leq 2000$