• 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