Let us fix the bottommost row of sub-rectangles to be counted.
Then, we can count for each column how many consecutive .s extend upward (starting from the current row).

For example, if we fix the bottommost row to the lowest row in the grid, the numbers of .s extending upward in the columns are \(h=(0,2,1,4,5)\).

...#.
.#...
###..
..#..
#....

If we can process this sequence \(h\) in \(O(M)\) time to count desired sub-rectangles, then the original problem can be solved in a total of \(O(NM)\) time.

For this sequence \(h\), we construct a Cartesian Tree. Reference 1 (Japanese) Reference 2 (Japanese) Wikipedia
Here, we somehow adopt a tie-break to those elements with the same value \(h_i\).
Once we find this Cartesian Tree, we can find values \(l\) and \(r\) defined for each \(i\) so that:

• \(h_j < h_i\) for \(j=l-1\);
• \(h_j > h_i\) for \(j=l,l+1,\dots,i-1,i+1\dots,r\);
• \(h_j < h_i\) for \(j=r+1\).

These \(l\) and \(r\) allow us to count all rectangular regions containing the \(i\)-th column, and \(h_i\) ranks the smallest. Here, the height of the rectangular region is constrained to \(h_i\).
For regions with smaller width, the height is constrained to \(h_i\); for those with larger width, the height is constrained to \(K\).
For each width, there are \((1,2,3,\dots,x-1,x,\dots,x,x-1,\dots,2,1)\) ways to choose rectangle of that width.
We omit the remaining details, but one can appropriately construct cumulative sums to express this contribution so that the number of rectangles can be counted in \(O(1)\) time for each \(i\).

Hence, the problem has been solved in \(O(NM)\) time.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

// https://nyaannyaan.github.io/library/tree/cartesian-tree.hpp.html
template <typename T>
pair<vector<vector<int>>, int> CartesianTree(vector<T> &a) {
  int N = (int)a.size();
  vector<vector<int>> g(N);
  vector<int> p(N, -1), st;
  st.reserve(N);
  for (int i = 0; i < N; i++) {
    int prv = -1;
    while (!st.empty() && a[i] < a[st.back()]) {
      prv = st.back();
      st.pop_back();
    }
    if (prv != -1) p[prv] = i;
    if (!st.empty()) p[i] = st.back();
    st.push_back(i);
  }
  int root = -1;
  for (int i = 0; i < N; i++) {
    if (p[i] != -1)
      g[p[i]].push_back(i);
    else
      root = i;
  }
  return make_pair(g, root);
}

int main(){
  long long n,m,k;
  cin >> n >> m >> k;
  vector<string> s(n);
  for(auto &nx : s){
    cin >> nx;
  }

  vector<vector<long long>> rw(6,vector<long long>(m+1,0));
  for(long long i=1;i<=m;i++){
    rw[0][i]=rw[0][i-1]+(k/i)*i;
    rw[1][i]=rw[1][i-1]+(k/i);
    rw[2][i]=rw[2][i-1]+(k/i)*(m+1-i);
    rw[3][i]=rw[3][i-1]+1*i;
    rw[4][i]=rw[4][i-1]+1;
    rw[5][i]=rw[5][i-1]+1*(m+1-i);
  }

  long long res=0;
  vector<long long> h(m,0);
  for(long long d=0;d<n;d++){
    for(long long i=0;i<m;i++){
      if(s[d][i]=='#'){h[i]=0;}
      else{h[i]++;}
    }
    auto [g,r]=CartesianTree(h);
    vector<long long> sq;
    queue<long long> q;
    q.push(r);
    while(!q.empty()){
      auto od=q.front(); q.pop();
      sq.push_back(od);
      for(auto &nx : g[od]){
        q.push(nx);
      }
    }
    reverse(sq.begin(),sq.end());
    vector<pair<long long,long long>> vp;
    for(long long i=0;i<m;i++){vp.push_back({i,i});}
    for(auto &nx : sq){
      for(auto &ny : g[nx]){
        vp[nx].first=min(vp[nx].first,vp[ny].first);
        vp[nx].second=max(vp[nx].second,vp[ny].second);
      }
      long long ch=h[nx];
      long long m0=1;
      long long m1=min(nx-vp[nx].first,vp[nx].second-nx)+1;
      long long m2=max(nx-vp[nx].first,vp[nx].second-nx)+1;
      long long m3=(vp[nx].second-vp[nx].first)+1;
      if(ch==0){continue;}
      {
        // unlimited
        long long l=(k/(ch+1))+1,r=1e9;
        {
          long long cl=max(l,m0),cr=min(r,m1);
          l=max(l,cr+1);
          if(cl<=cr){
            res+=rw[0][cr];
            res-=rw[0][cl-1];
          }
        }
        {
          long long cl=max(l,m1+1),cr=min(r,m2);
          l=max(l,cr+1);
          if(cl<=cr){
            res+=rw[1][cr]*m1;
            res-=rw[1][cl-1]*m1;
          }
        }
        {
          long long cl=max(l,m2+1),cr=min(r,m3);
          l=max(l,cr+1);
          if(cl<=cr){
            res+=rw[2][cr];
            res-=rw[2][cl-1];
            res-=rw[1][cr]*(m-m3);
            res+=rw[1][cl-1]*(m-m3);
          }
        }
      }
      {
        // limited
        long long l=1,r=(k/(ch+1));
        {
          long long cl=max(l,m0),cr=min(r,m1);
          l=max(l,cr+1);
          if(cl<=cr){
            res+=rw[3][cr]*ch;
            res-=rw[3][cl-1]*ch;
          }
        }
        {
          long long cl=max(l,m1+1),cr=min(r,m2);
          l=max(l,cr+1);
          if(cl<=cr){
            res+=rw[4][cr]*m1*ch;
            res-=rw[4][cl-1]*m1*ch;
          }
        }
        {
          long long cl=max(l,m2+1),cr=min(r,m3);
          l=max(l,cr+1);
          if(cl<=cr){
            res+=rw[5][cr]*ch;
            res-=rw[5][cl-1]*ch;
            res-=rw[4][cr]*(m-m3)*ch;
            res+=rw[4][cl-1]*(m-m3)*ch;
          }
        }
      }
    }
  }
  cout << res << "\n";
  return 0;
}