CSES - Datatähti 2016 alku - Tontti
  • Time limit: 1.00 s
  • Memory limit: 128 MB
Uolevi haluaa ostaa metsästä tontin, joka on neliön muotoinen ja jossa on tarkalleen $x$ puuta. Kuinka monta tapaa Uolevilla on tontin valintaan?

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua $n$, $m$ ja $x$: metsän korkeus, metsän leveys ja haluttu puiden määrä.

Tämän jälkeen syötteessä on $n$ riviä, joista jokaisella on $m$ merkkiä. Nämä rivit kuvaavat metsän. Merkki . tarkoittaa tyhjää kohtaa, ja merkki * tarkoittaa puuta.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: montako tapaa Uolevilla on tontin valintaan?

Esimerkki

Syöte:
4 6 3
..**..
**....
*...*.
..*...


Tuloste:
3

Rajat

Kaikissa osatehtävissä pätee:
  • $0 \le x \le n \cdot m$
Osatehtävä 1 (14 pistettä)
  • $1 \le n, m \le 10$
Osatehtävä 2 (33 pistettä)
  • $1 \le n, m \le 500$
Osatehtävä 3 (53 pistettä)
  • $1 \le n, m \le 2000$