P3654 First Step (ファーストステップ)

> Everything is full of things I don't know (what should I do?). Everything is entirely full of unknowns (what should I do?). Even so, my steps feel light with anticipation (jump!). But I still have light steps because I’m full of expectation (jump!). Someday we’ll make this gap in enthusiasm disappear. That cold attitude will one day disappear without a trace. I’m fine—I’ll cheer up and keep going. Show your energy, lift your spirits, and move forward.  We, Aqours, are going to hold our first concert! Although the student council president doesn’t seem very supportive, with the chairwoman’s backing, we’ve been allowed to sing on the school’s basketball court! The song is ready, titled “[If you really love it, it will be all right! (ダイスキだったらダイジョウブ！)](https://zh.moegirl.org/%E6%9C%80%E5%96%9C%E6%AC%A2%E7%9A%84%E8%AF%9D%E5%B0%B1%E6%B2%A1%E9%97%AE%E9%A2%98)”, and I’m sure everyone will like it! The concert will definitely go smoothly! I hope nothing like a power outage happens...!

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?

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 the total number of possible placements.

| | $R$ | $C$ | $K$ | Notes | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1\sim2$ | $\leq 10$ | $\leq 10$ | $\leq \min(R, C)$ | None | | $3\sim4$ | $\leq 100$ | $\leq 100$ | $\leq 1$ | None | | $5\sim6$ | $\leq 100$ | $\leq 100$ | $\leq \min(R, C)$ | No obstacles | | $7\sim10$ | $\leq 100$ | $\leq 100$ | $\leq \min(R, C)$ | None | 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