题目描述

你需要构造一个 $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