Ruudukko

from itertools import permutations
from math import factorial
import functools
from sys import exit


n = int(input())
board = [input() for _ in range(n)]

class _Any:
    __slots__ = ()

    def __eq__(self, other):
        return True

Any = _Any()


@functools.lru_cache(maxsize=500)
def derangement(n):
    if n == 1:
        return 0
    if n == 0:
        return 1
    
    return (n - 1) * (derangement(n - 1) + derangement(n - 2))

if all(set(row) == {'.'} for row in board):
    print((factorial(n) * derangement(n)) % (10 ** 9 + 7))
    exit(0)


indices_a = []
indices_b = []
for row in board:
    try:
        indices_a.append(row.index('A'))
    except ValueError:
        indices_a.append(Any)

    try:
        indices_b.append(row.index('B'))
    except ValueError:
        indices_b.append(Any)

total = 0
for p1 in permutations(range(n)):
    for p2 in permutations(range(n)):
        if any(x == y for x, y in zip(p1, p2)):
            continue

        if not all(x == y for x, y in zip(p1, indices_a)):
            continue
        
        if not all(x == y for x, y in zip(p2, indices_b)):
            continue
        
        total += 1

print(total)

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 29, in <module>
    print(...

Test 16

Group: 2

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 29, in <module>
    print(...

Test 17

Group: 2

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 29, in <module>
    print(...

Test 18

Group: 2

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 29, in <module>
    print(...

Test 19

Group: 2

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 29, in <module>
    print(...

Test 20

Group: 2

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 29, in <module>
    print(...

Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 29

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 3

Verdict: TIME LIMIT EXCEEDED