Crni

Παρόλο που έχει βρει όλες τις πιο διασκεδαστικές βόλτες, ο ενθουσιασμός του Mirko εξακολουθεί να μην ξεθωριάζει. Άνοιξε το τετράδιό του με γραφικό χαρτί και άρχισε να χρωματίζει τετράγωνα, και ένα νέο, ακόμη πιο δύσκολο πρόβλημα εμφανίστηκε πάνω του.

Σας δίνεται ένας τετράγωνος πίνακας που αποτελείται από ~N~ σειρές και ~N~ στήλες. Κάθε κελί είναι είτε μαύρο είτε λευκό.

Ένα σύνολο κελιών που σχηματίζουν ένα ορθογώνιο, με οριζόντιες και κάθετες ακμές να ακολουθούν τα όρια κελιών, ονομάζεται μαύρο ορθογώνιο εάν όλα τα κελιά μέσα στο ορθογώνιο είναι μαύρα και αποτελείται από τουλάχιστον δύο κελιά.

Η αριστερή εικόνα δείχνει δύο ορθογώνια που δεν είναι μαύρα ορθογώνια. Το ορθογώνιο με την ένδειξη 1 δεν είναι μαύρο ορθογώνιο επειδή περιέχει ένα λευκό κελί και το ορθογώνιο με την ετικέτα 2 δεν είναι μαύρο ορθογώνιο επειδή αποτελείται από ένα μόνο κελί. Από την άλλη πλευρά, η δεξιά εικόνα δείχνει τρία έγκυρα μαύρα ορθογώνια.

Υπολογίστε τον αριθμό των πιθανών επιλογών δύο μαύρων ορθογωνίων που δεν έχουν κοινά κελιά. Καθώς ο απαιτούμενος αριθμός μπορεί να είναι εξαιρετικά μεγάλος, θα πρέπει να εξάγετε το υπόλοιπο της διαίρεσης αυτού του αριθμού με το ~10\,007~.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο ~N\;(2 \leq N \leq 1000)~.

Κάθε μία από τις επόμενες ~N~ γραμμές περιέχει μία μόνο σειρά του πίνακα, που αποτελείται από ~N~ σύμβολα. Το σύμβολο "C" αντιπροσωπεύει ένα μαύρο κελί, ενώ το "Β" αντιπροσωπεύει ένα λευκό κελί.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει το υπόλοιπο της διαίρεσης του απαιτούμενου αριθμού με το ~10\,007~.

Παραδείγματα

input

2
CC
CC

output

2

input

3
CCB
CCB
CBB

output

5

input

5
BCCBB
BBCBB
BCCBB
BBBBB
CCBBB

output

8