Counting Disjoint Black Rectangles

Given an n × n grid where each cell is colored either black or white, we define a black rectangle as a sub-rectangle (formed by selecting two distinct rows and two distinct columns, or a rectangle containing at least 2 cells) in which every cell is black.

Your task is to count the number of ways to choose two black rectangles that do not share any common cell. Since the answer may be very large, output the count modulo \(10^4+7\) (i.e. modulo 10007).

Note: Two rectangles are disjoint if their cell sets do not intersect. In other words, if rectangle A covers rows from \(r_1\) to \(r_2\) and columns \(c_1\) to \(c_2\), and rectangle B covers rows \(r_3\) to \(r_4\) and columns \(c_3\) to \(c_4\), then they are disjoint if at least one of the following holds: \(r_2 < r_3\), \(r_4 < r_1\), \(c_2 < c_3\), or \(c_4 < c_1\).

inputFormat

The first line contains a single integer n representing the size of the grid. The following n lines each contain a string of length n consisting of the characters 'B' (for black) or 'W' (for white) which describe the grid.

It is guaranteed that 1 ≤ n ≤ 10 (or a small number so that a brute force solution is feasible).

outputFormat

Output a single integer, the number of ways to choose two disjoint black rectangles, taken modulo \(10^4+7\) (i.e. 10007).

sample

2
BB
BB

2