Tehtäväsi on sijoittaa n \times n -ruudukkoon merkkejä A ja B niin, että jokaisessa ruudussa on enintään yksi merkki ja jokaisella pysty- ja vaakarivillä on tarkalleen yksi merkki A ja yksi merkki B.

Lisähaasteena osa merkeistä on sijoitettu valmiiksi. Monellako tavalla voit täydentää ruudukon valmiiksi?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: ruudukon koko.

Tämän jälkeen syötteessä on n riviä, jotka kuvaavat ruudukon alkutilanteen. Jokaisella rivillä on n merkkiä. Merkki . tarkoittaa tyhjää ruutua, ja merkit A ja B ilmaisevat valmiiksi ruudukossa olevat merkit.

Voit olettaa, että syötteessä jokaisella pysty- ja vaakarivillä on enintään yksi merkki A ja enintään yksi merkki B.

Tuloste

Tulosta yksi kokonaisluku: tehtävän vastaus modulo 10^9+7.

Esimerkki

Syöte:

5
.....
..AB.
.....
B....
...A.

Tuloste:

16

Osatehtävä 1 (31 pistettä)

• 2 \le n \le 5

Osatehtävä 2 (14 pistettä)

• 2 \le n \le 500
• ruudukossa ei ole valmiina mitään merkkejä

Osatehtävä 3 (55 pistettä)

• 2 \le n \le 500