Ruudukko

input/code.cpp: In function 'void sor()':
input/code.cpp:143:5: error: 'printStuff' was not declared in this scope
  if(printStuff) {
     ^~~~~~~~~~
input/code.cpp:143:5: note: suggested alternative: 'printf'
  if(printStuff) {
     ^~~~~~~~~~
     printf
input/code.cpp: In function 'int main()':
input/code.cpp:297:8: warning: unused variable 'hits' [-Wunused-variable]
   bool hits = false;
        ^~~~
input/code.cpp:319:8: warning: unused variable 'hits' [-Wunused-variable]
   bool hits = false;
        ^~~~
input/code.cpp:342:7: error: 'printStuff' was not declared in this scope
    if(printStuff) {
       ^~~~~~~~~~
input/code.cpp:342:7: note: suggested alternative: 'printf'
    if(printStuff) {
       ^~~~~~~~~~
       printf
input/code.cpp:368:7: error: 'printStuff' was not declared in this scope
    if(printStuff) {
       ^~~~~~~~~~
input/code.cpp:368:7: note: suggested alternative: 'printf'
    if(printStuff) {
       ^~~~~~~~~~
       printf
input/code.cpp:377:7: error: 'pri...

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

//bool printStuff = true;

typedef long long ll;

const int N = 555;
const int M = 1e9 + 7;

char t[N][N];

ll n;

int aA;
int amB;

void swaR(int a, int b) {
	for(int x = 1; x <= n; ++x) {
		char c = t[a][x];
		char d = t[b][x];
		t[a][x] = d;
		t[b][x] = c;
	}
}

void swaC(int a, int b) {
	for(int y = 1; y <= n; ++y) {
		char c = t[y][a];
		char d = t[y][b];
		t[y][a] = d;
		t[y][b] = c;
	}
}

void print() {

	for(int y = 1; y <= n; ++y) {
		for(int x = 1; x <= n; ++x) {
			cout << t[y][x];
		}
		cout << "\n";
	}
	cout << "\n";
}

void sor() {

	vector<int> broken;

	for(int y = n; y >= n - amB + 1; --y) {
		bool conB = false;
		for(int x = 1; x <= n; ++x) {
			if(t[y][x] == 'B') {
				conB = true;
				break;
			}
		}

		if(!conB) broken.push_back(y);
	}

	for(int y = n - amB; y >= 1; --y) {
		bool conB = false;
		for(int x = 1; x <= n; ++x) {
			if(t[y][x] == 'B') {
				conB = true;
				break;
			}
		}
		if(!conB) {
			continue;
		}
		int k = broken[broken.size() - 1];
		swaR(k, y);
		broken.pop_back();
	}


	for(int y = n; y >= n - amB + 1; --y) {
		int col = -1;
		for(int x = 1; x <= n; ++x) {
			if(t[y][x] == 'B') {
				col = x;
			}
		}
		swaC(n - y + 1, col);
	}

	aA = 0;
	for(int x = amB + 1; x <= n; ++x) {
		for(int y = n - amB; y >= 1; --y) {
			if(t[y][x] == 'A') {
				++aA;
			}
		}
	}

	for(int y = n - amB; y >= n - amB - aA + 1; --y) {
		bool conA = false;
		for(int x = amB + 1; x <= n; ++x) {
			if(t[y][x] == 'A') {
				conA = true;
				break;
			}
		}

		if(!conA) {
			broken.push_back(y);
		}
	}

	for(int y = n - amB - aA; y >= 1; --y) {
		bool conA = false;
		for(int x = amB + 1; x <= n; ++x) {
			if(t[y][x] == 'A') {
				conA = true;
				break;
			}
		}
		if(conA) {
			int k = broken[broken.size() - 1];
			swaR(k, y);
			broken.pop_back();
		}
	}


	for(int y = n - amB; y >= n - amB - aA + 1; --y) {
		int col = -1;
		for(int x = amB + 1; x <= n; ++x) {
			if(t[y][x] == 'A') {
				col = x;
				break;
			}
		}
		swaC(n - y + 1, col);
	}

	if(printStuff) {
		cout << n << "\n";
		print();
	}
}


ll dp[N][N];


void fillDP() {
	dp[0][0] = 1;
	for(int x = 1; x <= n; ++x) {
		dp[x][0] = dp[x-1][0]*x;
		dp[x][0] %= M;
	}

	for(ll y = 1; y <= n; ++y) {
		for(ll x = y; x <= n; ++x) {
			dp[x][y] = dp[x-1][y-1]*(x-y);
			dp[x][y] %= M;
			if(y == 1) continue;
			dp[x][y] += dp[x-1][y-2]*(y-1);
			dp[x][y] %= M;
		}
	}
}

ll exp(ll a, ll e) {
	if(e == 0) return 1;
	if(e%2 == 0)  {
		ll c = exp(a, e/2);
		return (c*c)%M;
	}
	ll c = exp(a, e-1);
	return (c*a)%M;
}

ll fact[N];
ll binom[N][N];

bool marked[N];

int main() {
	cin >> n;
	for(int y = 1; y <= n; ++y) {
		for(int x = 1; x <= n; ++x) {
			char c;
			cin >> c;
			t[y][x] = c;
			if(c == 'B') ++amB;
		}
	}
	sor();

	fillDP();
	fact[0] = 1;
	for(ll i = 1; i <= n; ++i) {
		fact[i] = fact[i-1]*i;
		fact[i] %= M;
	}
	for(int m = 0; m <= n; ++m) {
		for(int k = 0; k <= m; ++k) {
			ll b = fact[m];
			b *= exp(fact[k], M-2);
			b %= M;
			b *= exp(fact[m-k], M-2);
			b %= M;
			binom[m][k] = b;
		}
	}
	ll ans = 0;



	int a1 = 0;
	int a2 = 0;
	int a3 = 0;


	//calculate a2
	for(int y = 1; y <= n - amB - aA; ++y) {
		for(int x = 1; x <= amB; ++x) {
			if(t[y][x] == 'A') {
				++a2;
			}
		}
	}

	//calculate a3;

	for(int y = n - amB; y <= n; ++y) {
		for(int x = amB + aA + 1; x <= n; ++x) {
			if(t[y][x] == 'A') {
				++a3;
			}
		}
	}
	//calculate a1;
	for(int x = 1; x <= amB; ++x) {
		for(int y = n - amB + 1; y <= n; ++y) {
			if(t[y][x] == 'A') {
				++a1;

			}
		}
	}
/*
	for(int i = 0; i <= n; ++i) {
		for(int a = 0; a <= i; ++a) {
			cout << dp[i][a] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
*/
	int initialB = 0;
	//How many B:s have been hit initially

	for(int x = 1; x <= amB; ++x) {
		for(int y = 1; y <= n; ++y) {
			if(t[y][x] == 'A') {
				if(!marked[x]) {
					++initialB;
					marked[x] = true;
				}
			}
		}
	}
	for(int y = n - amB + 1; y <= n; ++y) {
		for(int x = amB + 1; x <= n; ++x) {
			if(t[y][x] == 'A') {
				if(!marked[n - y + 1]) {
					++initialB;
					marked[n-y+1] = true;
				}
			}
		}
	}

	int hitAbove = 0;
	int noHitAbove = 0;
	int hitRight = 0;
	int noHitRight = 0;

	for(int x = 1; x <= amB; ++x) {
		bool contains = false;
		for(int y = 1; y <= n; ++y) {
			if(t[y][x] == 'A') {
				contains = true;
				break;
			}
		}
		if(contains) continue;
		bool hits = false;
		for(int y = 1; y <= n; ++y) {
			if(t[y][x] == 'B') {
				if(marked[x]) {
					++noHitAbove;
				} else {
					++hitAbove;
				}
				break;
			}
		}
	}

	for(int y = n - amB + 1; y <= n; ++y) {
		bool contains = false;
		for(int x = 1; x <= n; ++x) {
			if(t[y][x] == 'A') {
				contains = true;
				break;
			}
		}
		if(contains) continue;
		bool hits = false;
		for(int x = 1; x <= n; ++x) {
			if(t[y][x] == 'B') {
				if(marked[x]) {
					++noHitRight;
				} else {
					++hitRight;
				}
				break;
			}
		}
	}


	for(ll f2 = max(a2, a3); f2 <= min((ll) amB - a1, n - amB - aA); ++f2) {
		for(int amountOfB = initialB; amountOfB <= amB; ++amountOfB) {
			//We will have amountOfB of B:s that have been hit
			//We have to hit amountOfB - initialB more
			ll A23 = 0;
			int t = amountOfB - initialB;
			if(t > f2 - a2 + f2 - a3) continue;
			int s = n - amB - aA;
			
			if(printStuff) {
				cout << "\n\n";
				cout << "The configuration we have: \n";
				cout << "We have to hit " << t << " more B:s\n";
				cout << "We should add " << f2 - a2 << " and " << f2 - a3 << " new ones \n";
				cout << "There are " << noHitAbove << " and " << noHitRight << " choices that do not hit\n";
				cout << "and " << hitAbove << " and " << hitRight << " choices that hit a new one \n";
			}
			for(int o2 = 0; o2 <= t; ++o2) {
				int d2 = f2 - a2;
				ll A2 = binom[noHitAbove][d2 - o2]*binom[hitAbove][o2];
				A2 %= M;
				A2 *= binom[s - a2][d2];
				A2 %= M;
				
				int o3 = t - o2;
				int d3 = f2 - a3;

				ll A3 = binom[hitRight - o2][o3] * binom[noHitRight + o2][d3];
				A3 %= M;
				A3 *= binom[s - a3][d3];
				A3 %= M;
				A23 += A2*A3;
				A23 %= M;

			}
			if(printStuff) {
				cout << "The result is, we have " << A23 << " choices for the A:s\n";
			}
			if(A23 == 0) continue;


			ll f1 = amB - f2;
			ll d1 = f1 - a1;
			ll A1 = dp[d1][amB- amountOfB];
			if(printStuff) {
				cout << "In this case we have " << A1 << " choices for A1\n";
				cout << "That's because we added " << d1 << " new A:s to the grid\n";
				cout << "and there are " << amB - amountOfB << " B:s in the small area\n";
			}
			ll f4 = n - 2*f2 - f1 - aA;

			ll A4 = 1;
			for(ll i = 1; i <= f4; ++i) {
				A4 *= i;
				A4 %= M;
			}


			ll B = dp[n - amB][aA + f4];

			ll cur = A23;
			cur %= M;
			cur *= A1;
			cur %= M;
			cur *= A4;
			cur %= M;
			cur *= B;
			cur %= M;
			if(printStuff) {
				cout << "Statistics for " << f2 << " " << amountOfB << "\n";
				cout << "Number of ways for A:s " << A1*A23*A4 << "\n";
				cout << "Number of ways for A1 is " << A1 << " and for A23 it's " << A23 << " and for A4 " << A4 << "\n";
				cout << "Number of ways for B:s " << B << "\n";
				cout << "Total number of ways: " << A1*A23*A4*B << "\n";
				cout << "\n\n";
			}
			ans += cur;
			ans %= M;
		}
	}

	cout << ans << "\n";


}