Sanalista

#include<bits/stdc++.h>
using namespace std;
long mod = 1e9+7;
int n;
long asd = 0;
//Kiitos mestari OEIS ;P
unordered_map<long long, long long> c;
long long aa(long long d) {
  if(d == 0) return 1;
  if(d == 1) return 0;
  if(c.count(d) != 0) return c[d];
  long long b = (d-1)*((aa(d-1)%mod)+(aa(d-2)%mod)); b %= mod;
  c[d] = b;
  return b;
}


void b(int y, vector<vector<char>> c,vector<bool> ay, vector<bool> by, vector<bool> ax, vector<bool> bx) {
  if(y >= n) {
    asd++;
    return;
  }
  if(by[y] != true) {
    for(int i = 0; i < n; i++) {
      if(bx[i] == false && c[y][i] == '.') {
	by[y] = true;
	bx[i] = true;
	c[y][i] = 'B';
	b(y+1,c,ay,by,ax,bx);
	c[y][i] = '.';
	by[y] = false;
	bx[i] = false;
      }
    }
  }
  else {
    b(y+1, c, ay, by, ax, bx);
  }
}

void a(int y, vector<vector<char>> c,vector<bool> ay, vector<bool> by, vector<bool> ax, vector<bool> bx) {
  if(y >= n) { b(0,c,ay,by,ax,bx); return; }
  if(ay[y] == false) {
    for(int i = 0; i < n; i++) {
      if(ax[i] == false && c[y][i] == '.') {
	ax[i] = true;
	c[y][i] = 'A';
	a(y+1,c,ay,by,ax,bx);
	c[y][i] = '.';
	ax[i] = false;
      }
    }
  }
  else {
    a(y+1, c, ay, by, ax, bx);
  }
}

long long fac(long long cd) {
  long long fc = 1;
  for(int i = 1; i <= cd; i++) {
    fc *= i; fc %=mod;
  }
  return fc;
}

int main() {
  cin >> n;
  if(n <= 5) {
    vector<vector<char>> c; c.resize(7, vector<char> (7));
    vector<bool> ay(7); vector<bool> by(7); vector<bool> ax(7); vector<bool> bx(7);
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
	cin >> c[i][j]; if(c[i][j] == 'A') { ax[j] = true; ay[i] = true; }
	if(c[i][j] == 'B') { bx[j] = true; by[i] = true; }      
      }
    }
    a(0,c,ay,by,ax,bx);
    cout << asd << "\n";
  }
  else {
    long long b = n;
    cout << (fac(b)*aa(b))%mod << "\n";
  }
}

Test 1

Verdict: WRONG ANSWER