[AHOI2013] 好方的蛇
题目描述
有一天,可爱的蛇心花怒放,把自己变成了一个正方形!但是她改变的时候
被induce了导致改变出了些问题....
按照预设,她应该变成一个 $N*N$ 的全黑正方形,但是这个正方形出现了一些白的格子...现在她的身体不幸出了些小反应,定义一个subsnake是一个至少有两格的全黑矩形。
![qwq](http://images.cnblogs.com/cnblogs_com/yifusuyi/1229574/o_1(1).jpg)
现在蛇想让你帮忙求一下一共有多少对不相交的subsnake,答案模10007。
输入输出格式
输入格式
第一行一个整数 $N$, 接下来 $N$ 行,每行一个长度为 $N$ 的字符串,如果是 $B$,那么是黑的,如果是 $W$ 那么是白的。
输出格式
一行一个整数,表示答案
输入输出样例
输入样例 #1
3
BBW
BBW
BWW
输出样例 #1
5
说明
$1~\leq~N~\leq~1000$