Counting Disjoint Subsnakes

One day, a cute snake transformed into a square! However, during the change something went awry so that some cells turned white. According to the original plan, the snake should have become an $N\times N$ fully black square, but some cells are white. A subsnake is defined as an all-black subrectangle with at least two cells. Your task is to count the number of pairs of non-intersecting subsnakes and output the answer modulo 10007.

inputFormat

The first line contains an integer $N$.
Each of the next $N$ lines contains a string of $N$ characters. Each character is either '1' (representing a black cell) or '0' (representing a white cell), which together describe the grid.

outputFormat

Output one integer: the number of pairs of disjoint subsnakes modulo 10007.

sample

2
11
11

2