Ruudukko

• Time limit: 1.00 s
• Memory limit: 512 MB

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$