CSES - Datatähti 2019 alku - Ruudukko
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Tehtäväsi on sijoittaa n×nn \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 nn: ruudukon koko.

Tämän jälkeen syötteessä on nn riviä, jotka kuvaavat ruudukon alkutilanteen. Jokaisella rivillä on nn 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 109+710^9+7.

Esimerkki

Syöte:

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

Tuloste:

16

Osatehtävä 1 (31 pistettä)

  • 2n52 \le n \le 5

Osatehtävä 2 (14 pistettä)

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

Osatehtävä 3 (55 pistettä)

  • 2n5002 \le n \le 500