Code Submission Evaluation System Login

Datatähti 2019 alku

Start:2018-10-01 00:00:00
End:2018-10-15 00:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - Datatähti 2019 alku - Ruudukko

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ä)
Osatehtävä 2 (14 pistettä)
Osatehtävä 3 (55 pistettä)