Description

However... this basketball court seems like it hasn’t been used for a long time.

It’s piled high with all kinds of school odds and ends.

How can the members of Aqours line up inside?

Our basketball court at Uranohoshi Girls’ High School is an $R$-by-$C$ grid. It is filled with various school items (denoted by #), and it looks like there isn’t much open space (denoted by .).

We now have $K$ members in Aqours. To sing and dance, we need to form a straight line of size $1 \times K$, standing one after another on empty cells in the court (either horizontally or vertically).

We want to know how many possible ways there are to stand.

As a true fan of Aqours, can you help us count?

Input Format

The first line contains three integers $R$, $C$, and $K$.

The following $R$ lines each contain $C$ characters, representing the basketball court of Uranohoshi Girls’ High School.

Output Format

Output the total number of possible placements.

5 5 2
.###.
##.#.
..#..
#..#.
#.###

8

Hint

For all testdata, $1 \leq R, C \leq 100$, $1 \leq K \leq \min(R, C)$.

Easter egg: In episode 3 of LoveLive! Sunshine!! season 1, when Chika Takami, the leader of Aqours, sings “If you really love it, it will be all right!” up to just before the chorus, the school loses power due to a lightning strike.

Translated by ChatGPT 5