#include using namespace std; using ll = long long; #define BR "\n" #define SP " " #define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << SP; } cout << BR; #define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << BR; ll H, W, K; ll ans; vector> board(2000, vector(2000)); set ,int>> visited; int c(vector x) { int temp; for (int i = 0; i < x.size(); i++) { if (x[i] > 0) temp++; } return temp; } void check(int sx, int sy, int ex, int ey, vector A) { visited.insert(make_pair(make_pair(sx, sy), ex - sx)); if (c(A) < K) return; if (c(A) == K) ans++; if (sx == ex) return; vector A1 = A; for (int i = sx; i <= ex; i++) { A1[board[i][sy]]--; } vector A11 = A1; for (int i = sy + 1; i <= ey; i++) { A11[board[sx][i]]--; } if (visited.find(make_pair(make_pair(sx + 1, sy + 1), ex - sx - 1)) == visited.end()) { check(sx + 1, sy + 1, ex, ey, A11); } vector A12 = A1; for (int i = sy + 1; i <= ey; i++) { A12[board[ex][i]]--; } if (visited.find(make_pair(make_pair(sx, sy + 1), ex - sx - 1)) == visited.end()) { check(sx, sy + 1, ex - 1, ey, A12); } vector A2 = A; for (int i = sx; i <= ex; i++) { A2[board[i][ey]]--; } vector A21 = A2; for (int i = sy; i <= ey - 1; i++) { A21[board[sx][i]]--; } if (visited.find(make_pair(make_pair(sx + 1, sy), ex - sx - 1)) == visited.end()) { check(sx + 1, sy, ex, ey - 1, A21); } vector A22 = A2; for (int i = sy; i <= ey - 1; i++) { A22[board[ex][i]]--; } if (visited.find(make_pair(make_pair(sx, sy), ex - sx - 1)) == visited.end()) { check(sx, sy, ex - 1, ey - 1, A22); } } int main() { cin >> H >> W >> K; vector a(26, 0); for (int i = 0; i < H; i++) { string s; cin >> s; for (int j = 0; j < s.size(); j++) { int alpha = s[j] - 'a'; board[i][j] = alpha; a[alpha]++; } } ans = 0; check(0, 0, H - 1, W - 1, a); cout << ans << BR; return 0; }