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

板块: Counting Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你的任务是创建一个 $n \times n$ 的网格，其中每一行和每一列恰好各有一个 A 和一个 B。部分字符已经放置好了。有多少种不同的方式可以完成这个网格？

输入

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

之后有 $n$ 行描述该网格，每行有 $n$ 个字符：. 表示空格，A 和 B 表示已经放置好的字符。

可以假定每行和每列最多只有一个 A 和一个 B。

输出

输出一个整数：完成方式的数量对 $10^9+7$ 取模。

数据范围

$2 \le n \le 500$

样例输入

5
.....
..AB.
.....
B....
...A.

样例输出

16