题目背景

翻译自 CSES-2429 题。

题目描述

你的任务是创建一个 $n \times n$ 的网格，其中每一行和每一列必须恰好包含一个 A 和一个 B。部分字符已经被预先放置。你需要计算完成这个网格的方式有多少种。

输入格式

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

接下来有 $n$ 行描述网格，每行包含 $n$ 个字符：. 表示一个空格，A 和 B 表示已经放置的字符。

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

输出格式

输出一个整数：表示补全网格的方式数，结果需对 $10^9 + 7$ 取模。

样例

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

16

说明/提示

$2 \leq n \leq 500$。