#include <cstdio>
#include <string>
#include <map>
#include <cstring>
#include <cassert>
using namespace std;

typedef unsigned long long llu;
struct node {
int  num;   // black - white
char a[9];  //the number of the grid even-white odd-black
char no;   //the forbideen color the 0-white 1-black 2-both can
char vwb;  //the valid color 0-white 1-black 2-both 3-neither
char dwb;  //0-dead white (Never can appear a white grid) 1-dead black 3-neither dead
};

int m,n,last,now,pp,un;
llu ans;
char s[10][10];


inline bool operator<(const node &a,const node &b) {
    if (a.no < b.no) {
        return true;
    }
    if (a.no > b.no) {
        return false;
    }
    if (a.dwb < b.dwb) {
        return true;
    }
    if (a.dwb > b.dwb) {
        return false;
    }
    if (a.vwb < b.vwb) {
        return true;
    }
    if (a.vwb > b.vwb) {
        return false;
    }
        if (a.num<b.num) {
            return true;
        }
        if (a.num>b.num) {
            return false;
        }
    for (int i = 0;i < n;++i) {
        if (a.a[i] < b.a[i]) {
            return true;
        }
        if (a.a[i] > b.a[i]) {
            return false;
        }
    }
    return false;
}

map<node,llu> save[2];

inline bool iswhite(int x) {
    return !(x & 1);
}

inline bool isblack(int x) {
    return (x & 1);
}

void makelone(node &temp,int y,int x,int n) {
int i,j,z = (y << 1) + x;
    temp.a[y] = z;
    z = (y << 1);
    for (i = y + 1;i < n;++i) {
        if (temp.a[i] == z) {
            break;
        }
    }
    for (j = i,i <<= 1; j < n; ++j) {
        if (temp.a[j] == z) {
            temp.a[j] = i;
        }
    }
    z = (y << 1) | 1;
    for (i = y + 1;i < n;++i) {
        if (temp.a[i] == z) {
            break;
        }
    }
    for (j = i,i = (i << 1) | 1;j < n;++j) {
        if (temp.a[j] == z) {
            temp.a[j] = i;
        }
    }

}

void makeunion(node &temp,int x,int y,int n) {
    if (x < y) {
        x ^= y ^= x ^= y;
    }
    for (int i = 0; i < n;++i) {
        if (temp.a[i] == x) {
            temp.a[i] = y;
        }
    }
}


void makewhite(int x,int y,node temp,llu ans,int add) {
bool yes;
int i,j,k,ll,uu;
map<node,llu>::iterator t;

    if ((temp.no == 0) || (temp.dwb == 0))  { 
        return;
    }
    temp.num += add;
    if ((temp.num + un < -pp) || (temp.num - un > pp)) {
        return;
    }
    yes = (temp.dwb == 1);

    if ((x) && (temp.a[y] == ((y << 1) | 1))) { //above is the head of black
        for (i = y + 1;i < n;++i) {
            if (temp.a[i] == temp.a[y]) {
                break;
            }
        }
        if (i >= n) {
            if ((temp.vwb != 1) && (temp.vwb != 2)) { //make black dead
                return;
            }
            yes = true;
        }
    }
    ll = ((y) && iswhite(temp.a[y - 1]))?temp.a[y - 1]:(-1);
    uu = ((x) && iswhite(temp.a[y]))?temp.a[y]:(-1);
    k = x?n:(y + 1);
    if (uu < 0) {
        makelone(temp, y,0 ,k);
        if (ll >= 0) {
            temp.a[y] = ll;
        }
    }
    else if ((ll >= 0) && (ll != uu)) {
        makeunion(temp,ll,uu,k);

    }
    for (i = j = 0;i < k;++i) {
        if ((temp.a[i]== (i<<1)) && (++j > 1)) {
            break;
        }
    }
    if (j == 1) {
        temp.vwb = ((temp.vwb == 1) || (temp.vwb == 2))?2:0;
    }
    else { //j > 1
        temp.vwb = ((temp.vwb == 1) || (temp.vwb == 2))?1:3;
    }
    temp.dwb = yes?1:3;
    temp.no = ((uu >= 0) && (y + 1 < n) && ((temp.a[y + 1] & 1) == 0))?0:2;
    save[now][temp] += ans;

}


void makeblack(int x,int y,node temp,llu ans,int add) {
bool yes;
int i,j,k,ll,uu;
map<node,llu>::iterator t;

    if ((temp.no == 1) || (temp.dwb == 1))  { 
        return;
    }
    temp.num += add;
    if ((temp.num + un < -pp) || (temp.num - un > pp)) {
        return;
    }

    yes = (temp.dwb == 0);
    if ((x) && (temp.a[y]==(y << 1))) { //above is the head of white
        for (i = y + 1;i < n;++i) {
            if (temp.a[i] == temp.a[y]) {
                break;
            }
        }
        if (i >= n) {
            if ((temp.vwb != 0) && (temp.vwb != 2)) { ///make black dead
                return;
            }
            yes = true;
        }
    }

    ll = ((y) && isblack(temp.a[ y - 1]))?temp.a[y - 1]:(-1);
    uu = ((x) && isblack(temp.a[y]))?temp.a[y]:(-1);
    k = x?n:(y + 1);
    if (uu < 0) {
        makelone(temp,y,1,k);
        if (ll >= 0) {
            temp.a[y] = ll;
        }
    }
    else if ((ll >= 0) && (ll != uu)) {
        makeunion(temp,ll,uu,k);
    }
    for (i = j = 0;i < k;++i) {
        if ((temp.a[i]==((i << 1) | 1)) && (++j > 1)) {
            break;
        }
    }
    if (j == 1) {
        temp.vwb = ((temp.vwb==0) || (temp.vwb==2))?2:1;
    }
    else { //j>1
        temp.vwb = ((temp.vwb==0) || (temp.vwb==2))?0:3;
    }
    temp.dwb = yes?0:3;
    temp.no = ((uu >= 0) && (y + 1 < n) && ((temp.a[ y + 1] & 1) == 1))?1:2;
    save[now][temp] += ans;

}


int main() {
int z;
node temp;
    scanf("%d%d%d",&m,&n,&pp);
    assert(0 <= m && m <= 8);
    assert(0 <= n && n <= 8);
    assert(0 <= pp <= m*n);
    memset(temp.a,0,sizeof(temp.a));
    temp.num = 0;
    temp.no = temp.vwb = 2;
    temp.dwb = 3;
    save[0].clear();
    un = 0;
    for (int i  = 0;i < m;++i) {
        scanf("%s",s[i]);
        for (int j = 0; j < n; ++j) {
            if (s[i][j] == 'T') {
                ++temp.num;
            }
            else if (s[i][j] == 'D') {
                --temp.num;
            }
            else {
                ++un;
            }
        }
    }
    save[last = 0][temp] = 1;
    //printf("un = %d\n",un);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n;++j) {
            save[now = 1 ^ last].clear();
            if (s[i][j] == 'U') {
                --un;
            }   
            for (map<node,llu>::iterator t = save[last].begin();t != save[last].end();++t) {
                if (s[i][j] == 'T') {
                    makeblack(i,j,t->first,t->second, 0);
                }
                else if (s[i][j] == 'D') {
                    makewhite(i,j,t->first,t->second, 0);
                }
                else {
                    makeblack(i,j,t->first,t->second, 1);
                    makewhite(i,j,t->first,t->second, -1);
                }
            }
            last = now;
        }

    }
    ans = 0;
    //printf("un = %d\n",un);
    assert(un == 0);
    for (map<node,llu>::iterator t = save[last].begin();t != save[last].end();++t) {
        if (t->first.vwb == 2) {
            assert((t->first.num >= -pp) && (t->first.num <= pp));
            //printf("%d %llu\n",t->first.num, t->second);
            ans += t->second;
        }
    }
    printf("%llu\n",ans);
    return 0;
}

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

	static int T = 0;
	static int D = 1;
	static int U = -1;
	
	static class Cell {
		int piece;  //0..1
		int groupIndex; //0...
		
		public Cell(int piece, int groupIndex) {
			this.piece = piece;
			this.groupIndex = groupIndex;
		}
		
		public String toString() {
			if(piece == 0) {
				return "" + (char)('a' + groupIndex);
			} else {
				return "" + (char)('A' + groupIndex);
			}
		}
		
		public boolean equals(Object o) {
			Cell other = (Cell)o;
			return piece == other.piece && groupIndex == other.groupIndex;
		}
		
		public int hashCode() {
			return 31 * piece + groupIndex;
		}

		public Cell copy() {
			return new Cell(piece, groupIndex);
		}
	}
	
	static class LineState {
		Cell[] cells;
		boolean isHidingGroup = false;

		public LineState(Cell[] cells) {
			this.cells = cells.clone();
		}
		
		public LineState(int template, int width) {
			cells = new Cell[width];
			for (int i = 0; i < width; i++) {
				cells[i] = new Cell(template % 2, -1);
				template /= 2;
			}
		}
		
		public boolean isMatch(int[] constraint) {
			for (int i = 0; i < cells.length; i++) {
				if(constraint[i] >= 0 && constraint[i] != cells[i].piece) {
					return false;
				}
			}
			return true;
		}
		
		public int countOnes() {
			int c = 0;
			for (int i = 0; i < cells.length; i++) {
				c += cells[i].piece;
			}
			return c;
		}
		
		public boolean isOfTwoPieces() {
			if(isHidingGroup && isUniform()) return true;
			for (int i = 0; i < cells.length; i++) {
				if(cells[i].groupIndex > 0) return false;
			}
			return true;
		}
		
		public String toString() {
			StringBuilder sb = new StringBuilder();
			for (Cell c: cells) {
				sb.append(c);
			}
			if(isHidingGroup) sb.append("!");
			return sb.toString();
		}
		
		public boolean equals(Object o) {
			LineState other = (LineState)o;
			return toString().equals(other.toString());
		}
		
		public LineState copy() {
			Cell[] cs = new Cell[cells.length];
			for (int i = 0; i < cs.length; i++) {
				cs[i] = cells[i].copy();
			}
			LineState copy = new LineState(cs);
			copy.isHidingGroup = isHidingGroup;
			return copy;
		}
		
		boolean isUniform() {
			int p = cells[0].piece;
			for (int i = 1; i < cells.length; i++) {
				if(cells[i].piece != p) return false;
			}
			return true;
		}
		
		public void revalidate() {
			int g0 = 20;
			int g1 = 20;

			for (int i = 0; i < cells.length; i++) {
				int g = cells[i].groupIndex;
				if(g >= 0) continue;
				int p = cells[i].piece;
				if(p == 0) {
					for (int j = i; j < cells.length && cells[j].piece == p && cells[j].groupIndex < 0; j++) {
						cells[j].groupIndex = g0;
					}
					g0++;
				} else {
					for (int j = i; j < cells.length && cells[j].piece == p && cells[j].groupIndex < 0; j++) {
						cells[j].groupIndex = g1;
					}
					g1++;
				}
			}
			
			int[] m0 = new int[cells.length + 20];
			int[] m1 = new int[cells.length + 20];
			for (int i = 0; i < m0.length; i++) {
				m0[i] = -1;
				m1[i] = -1;
			}
			g0 = 0;
			g1 = 0;
			
			for (int i = 0; i < cells.length; i++) {
				int g = cells[i].groupIndex;
				if(g < 0) continue;
				if(cells[i].piece == 0) {
					if(m0[g] >= 0) {
						cells[i].groupIndex = m0[g];
					} else {
						m0[g] = g0;
						cells[i].groupIndex = g0;
						g0++;
					}
				} else {
					if(m1[g] >= 0) {
						cells[i].groupIndex = m1[g];
					} else {
						m1[g] = g1;
						cells[i].groupIndex = g1;
						g1++;
					}
				}
			}
			
		}
	}
	
	int width;
	int height;
	int diff;
	int[][] constraint;
	
	Map<String, LineState> states = new HashMap<>();
	Map<String, Set<String>> transfers = new HashMap<>();
	Map<String, Map<Integer,Long>> counts = new HashMap<>();
	
	public void setSize(int width, int height, int diff) {
		this.width = width;
		this.height = height;
		this.diff = diff;
	}
	
	public void setConstraint(int[][] constraint) {
		this.constraint = constraint;
	}

	
	public List<LineState> createState() {
		List<LineState> states = new ArrayList<>();
		int t = 0;
		Cell[] cells = new Cell[width];
		int[] way = new int[width + 1];
		int[] wayCount = new int[width + 1];
		Cell[][] ways = new Cell[width + 1][width + 1];
		ways[0][0] = new Cell(0, 0);
		ways[0][1] = new Cell(1, 0);
		wayCount[0] = 2;
		way[t] = -1;
		while(true) {
			while(way[t] == wayCount[t] - 1) {
				if(t == 0) return states;
				t--;
			}
			way[t]++;
			cells[t] = ways[t][way[t]];
			t++;
			wayCount[t] = 0;
			if(t < width) {
				int p = cells[t-1].piece;
				ways[t][0] = new Cell(p,  cells[t-1].groupIndex); //same
				wayCount[t]++;
				List<Cell> gStack = new ArrayList<>();
				int g = -1;
				for (int i = 0; i < t; i++) {
					int j = gStack.indexOf(cells[i]);
					if(j >= 0) {
						while(gStack.size() > j + 1) gStack.remove(gStack.size() - 1);
					} else {
						gStack.add(cells[i]);
						if(cells[i].piece == 1 - p) {
							if(cells[i].groupIndex > g) g = cells[i].groupIndex;
						}
					}
				}
				for (Cell c: gStack) {
					if(c.piece == 1 - p) {
						ways[t][wayCount[t]] = c;
						wayCount[t]++;
					}
				}
				ways[t][wayCount[t]] = new Cell(1-p,  g+1);
				wayCount[t]++;
			} else {
				states.add(new LineState(cells));
			}
			way[t] = -1;
		}
	}
	
	//to - template
	public LineState transfer(LineState from, LineState to) {
		if(from.isHidingGroup) {
			if(width == 1 && from.cells[0].piece == to.cells[0].piece) {
				to = to.copy();
				to.isHidingGroup = true;
				to.revalidate();
				return to;
			}
			return null;
		}
		for (int i = 0; i < from.cells.length - 1; i++) {
			int p = from.cells[i].piece;
			if(p == from.cells[i + 1].piece && p == to.cells[i].piece
					 && p == to.cells[i + 1].piece) {
				return null; //square 2x2
			}
		}
		from = from.copy();
		to = to.copy();
		for (int i = 0; i < from.cells.length; i++) {
			to.cells[i].groupIndex = -1;
		}
		for (int i = 0; i < from.cells.length; i++) {
			int p = from.cells[i].piece;
			int g1 = from.cells[i].groupIndex;
			int g2 = to.cells[i].groupIndex;
			if(p == to.cells[i].piece && g1 != g2) {
				if(g2 >= 0) {
					for (int j = 0; j < from.cells.length; j++) {
						int ga = (g1 < g2) ? g1 : g2;
						int gb = (g1 > g2) ? g1 : g2;
						if(p == from.cells[j].piece && gb == from.cells[j].groupIndex) {
							from.cells[j].groupIndex = ga;
						}
						if(p == to.cells[j].piece && gb == to.cells[j].groupIndex) {
							to.cells[j].groupIndex = ga;
						}
					}
				} else {
					to.cells[i].groupIndex = g1;
					int j = i + 1;
					while(j < from.cells.length && to.cells[j].piece == p) {
						to.cells[j].groupIndex = g1;
						j++;
					}
					j = i - 1;
					while(j >= 0 && to.cells[j].piece == p) {
						to.cells[j].groupIndex = g1;
						j--;
					}
				}
			}
		}
		Set<Cell> accounted = new HashSet<>();
		for (int i = 0; i < from.cells.length; i++) {
			if(from.cells[i].piece == to.cells[i].piece) {
				accounted.add(from.cells[i]);
			}
		}
		Set<Cell> unaccounted = new HashSet<>();
		for (int i = 0; i < from.cells.length; i++) {
			if(!accounted.contains(from.cells[i]) && !unaccounted.contains(from.cells[i])) {
				unaccounted.add(from.cells[i]);
			}
		}
		if(unaccounted.size() > 1) return null;
		to.revalidate();
		if(unaccounted.size() == 1) {
			if(!to.isUniform()) {
				return null;
			} else {
				to.isHidingGroup = true;
			}
		}		
		return to;
	}
	
	public void build() {
		int p2 = 1;
		for (int i = 0; i < width; i++) p2 *= 2;
		List<LineState> states = createState();
		for (LineState s: states) {
			this.states.put(s.toString(), s);
			if(s.isUniform()) {
				LineState s1 = s.copy();
				s1.isHidingGroup = true;
				this.states.put(s1.toString(), s1);
			}
		}
		for (LineState s: this.states.values()) {
			Set<String> ts = new HashSet<>();
			for (int i = 0; i < p2; i++) {
				LineState t = new LineState(i, width);
				t = transfer(s, t);
				if(t != null) ts.add(t.toString());
			}
			transfers.put(s.toString(), ts);
		}
		for (int i = 0; i < p2; i++) {
			LineState t = new LineState(i, width);
			t.revalidate();
			if(!t.isMatch(constraint[0])) continue;
			Map<Integer, Long> v = new HashMap<>();
			v.put(t.countOnes(), 1l);
			counts.put(t.toString(), v);
		}
		for (int i = 0; i < height - 1; i++) {
			counts = addRow(counts, constraint[i+1]);
		}
		long sum = sum(counts, diff, width * height);
		System.out.println(sum);
	}
	
	Map<String, Map<Integer,Long>> addRow(Map<String, Map<Integer,Long>> counts, int[] cs) {
		Map<String, Map<Integer,Long>> next = new HashMap<>();
		for (String s: counts.keySet()) {
			Map<Integer, Long> vs = counts.get(s);
			for (String n: transfers.get(s)) {
				LineState t = states.get(n);
				if(!t.isMatch(cs)) continue;
				int dk = t.countOnes();
				if(!next.containsKey(n)) {
					Map<Integer, Long> v = new HashMap<>();
					for (int k: vs.keySet()) {
						v.put(k + dk, vs.get(k));
					}
					next.put(n, v);
				} else {
					Map<Integer, Long> v = next.get(n);
					for (int k: vs.keySet()) {
						if(!v.containsKey(k + dk)) {
							v.put(k + dk, vs.get(k));
						} else {
							v.put(k + dk, v.get(k + dk) + vs.get(k));
						}
					}
				}
			}
		}
		return next;
	}
	
	long sum(Map<String, Map<Integer,Long>> counts, int diff, int size) {
		long result = 0;
		for (String s: counts.keySet()) {
			LineState state = states.get(s);
			if(state.isOfTwoPieces()) {
				for (int k: counts.get(s).keySet()) {
					int k1 = size - k;
					if(Math.abs(k - k1) <= diff) {
						long d = counts.get(s).get(k);
						result += d;
					}
				}
			}
		}
		return result;
	}

	public void run() {
		Scanner in = new Scanner(System.in);
		int m = in.nextInt(), n = in.nextInt(), k = in.nextInt();
		if(m == 0 || n == 0) {
			System.out.println(1);
			return;
		}
//		in.next();
		setSize(n, m, k);
		int[][] cs = new int[m][n];
		for (int i = 0; i < m; i++) {
			String s = in.next();
			for (int j = 0; j < n; j++) {
				char ch = s.charAt(j);
				cs[i][j] = ch == 'T' ? T : ch == 'D' ? D : U;
			}
		}
		setConstraint(cs);
		build();
	}

    public static void main(String[] args) {
        new Solution().run();
    }
}
 

# Enter your code here. Read input from STDIN. Print output to STDOUT

from collections import defaultdict

M, N, K = (int(s) for s in raw_input().split())

sa=[]
D=[]
T=[]
max_d=-1
max_t=-1
for i in range(M):
    sa.append(raw_input())
if (N>M):
    sa=map(''.join ,zip(*sa))
    N,M=M,N
if (N==1):
    sa=map(''.join ,zip(*sa))
    N,M=M,N
    
for i in range(M):       
    s=sa[i][:N]
    sd = s
    st = s
    sd = sd.replace("U","0")
    sd = sd.replace("D","1")
    sd = sd.replace("T","0")
    if int(sd,2)!=0:
        max_d=i
    D.append(int(sd,2))
    st = st.replace("U","0")
    st = st.replace("D","0")
    st = st.replace("T","1")
    if int(sd,2)!=0:
        max_t=i
    T.append(int(st,2))

if (N%2==0)and(M%2==0):
    max_K = (N+M-1)        
else:
    max_K = (N+M+1)
max_K = max(max_K,4)
do_K = (K<max_K)    
    
def transfer(prev_comb, comb_compact):
        temp_comb_compact=comb_compact
        comb=[]
        for _ in range(N):
            comb.append(2*(temp_comb_compact%2)-1)
            temp_comb_compact /=2

        if prev_comb:
            label0_prev=-min(min(prev_comb),0)
            label1_prev=max(max(prev_comb),0)
        else:     
            prev_comb=[0]*N
            label0_prev=0
            label1_prev=0

        N_full=N+label0_prev+label1_prev+1
        N_half=N+label0_prev
        label = [0]*N_full
        adj = [[] for _ in range(N_full)]
        for i in range(N-1):
            if comb[i]*comb[i+1]>0:
                adj[i].append(i+1)
                adj[i+1].append(i)
                if (prev_comb[i]*prev_comb[i+1]>0)and(comb[i]*prev_comb[i]>0):
                    return []

        for i in range(N):
            prev_level = prev_comb[i]
            if comb[i]*prev_level>0:
                adj[i].append(N_half+prev_level)
                adj[N_half+prev_level].append(i)
    
        plus_label=0
        minus_label=0

        for i in range(N):
            if not(label[i])and(comb[i]!=0):
                if comb[i]>0:
                    plus_label += 1
                    current_label = plus_label
                elif comb[i]<0:
                    minus_label -= 1
                    current_label =minus_label
                label[i] = current_label
            
                q=[]
                q.append(i)
                while q:
                    node = q.pop()
                    for node_neighbour in adj[node]:
                        if not label[node_neighbour]:
                            label[node_neighbour] = current_label
                            q.append(node_neighbour)

        if (label0_prev>0)and(max(label[N:N_half])==0)and((label0_prev>1)or((label0_prev==1)and(minus_label!=0))):
            return []
        if (label1_prev>0)and(min(label[N_half+1:N_full])==0)and((label1_prev>1)or((label1_prev==1)and(plus_label!=0))):        
            return []

        return (tuple(label[:N]))


transfer_matrix=[]
transfer_matrix_end=[]
label_to_index={}
number_of_comb=[]
end_labels =[]

def build_transfer_matrix():
    N_labels = 0       
    pow2N=pow(2,N)
    queue_to_process = []
    for comb in range(pow2N):        
        labeled_comb = transfer([], comb)
        if labeled_comb:
            label_to_index[labeled_comb] = N_labels
            if (max(labeled_comb)<=1)and(min(labeled_comb)>=-1):
                end_labels.append(N_labels)
            queue_to_process.append([labeled_comb, N_labels])
            N_labels+=1
            transfer_matrix.append([])
            transfer_matrix_end.append([])
            if (comb&T[0]!=0)or(~comb&D[0]!=0):
                number_of_comb.append(0)
            else:
                number_of_comb.append(1)

    while queue_to_process:
        prev = queue_to_process.pop()
        prev_label = prev[0] 
        prev_index = prev[1]

        for comb in range(pow2N):
        
            labeled_comb = transfer(prev_label, comb)
            if labeled_comb:
                if labeled_comb not in label_to_index:
                    label_to_index[labeled_comb] = N_labels
                    if (max(labeled_comb)<=1)and(min(labeled_comb)>=-1):
                        end_labels.append(N_labels)
                    queue_to_process.append([labeled_comb, N_labels])
                    next_index = N_labels
                    N_labels+=1
                    transfer_matrix.append([])
                    transfer_matrix_end.append([])
                    number_of_comb.append(0)
                else:
                    next_index = label_to_index[labeled_comb]
                if (comb == 0)or(comb==pow2N-1):
                    transfer_matrix_end[prev_index].append([next_index,comb])
                else:
                    transfer_matrix[prev_index].append([next_index,comb])

build_transfer_matrix()

if do_K:
  K_lt = [2*bin(i).count("1")-N for i in range(pow(2,N))]

  prev_number_of_comb= number_of_comb
  number_of_comb=[[0]*(2*max_K+1) for _ in range(len(number_of_comb))]
  for comb in range(pow(2,N)):
    number_of_comb[comb][K_lt[comb]+max_K]=prev_number_of_comb[comb]
  
  for row in range(1,M):
    prev_number_of_comb= number_of_comb
    number_of_comb=[[0]*(2*max_K+1) for _ in range(len(number_of_comb))]
    for prev_id in range(len(transfer_matrix)):
        for K_id in range(2*max_K+1):
            if prev_number_of_comb[prev_id][K_id]: 
                for next_id,next_comb in transfer_matrix[prev_id]:      
                    if (next_comb&T[row]==0)and(~next_comb&D[row]==0)and(abs(K_id-max_K+K_lt[next_comb])<=max_K):
                        number_of_comb[next_id][K_id+K_lt[next_comb]]+=prev_number_of_comb[prev_id][K_id]

    if row==M-1:  
        for prev_id in range(len(transfer_matrix_end)):
            for K_id in range(2*max_K+1):
                if transfer_matrix_end[prev_id]:
                    for next_id,next_comb in transfer_matrix_end[prev_id]:
                        if (next_comb&T[M-1]==0)and(~next_comb&D[M-1]==0) and (abs(K_id-max_K+K_lt[next_comb])<=max_K):
                            number_of_comb[next_id][K_id+K_lt[next_comb]]+=prev_number_of_comb[prev_id][K_id]

  final_sum=0
  for end_id in end_labels:
    for K_id in range(2*max_K+1):
        if abs(K_id-max_K)<=K:
            final_sum+=number_of_comb[end_id][K_id]
  print final_sum

else:
  for row in range(1,M):
    prev_number_of_comb= number_of_comb
    number_of_comb=[0]*len(number_of_comb)
    for prev_id in range(len(transfer_matrix)):
        if prev_number_of_comb[prev_id]: 
            for next_id,next_comb in transfer_matrix[prev_id]:      
                if (next_comb&T[row]==0)and(~next_comb&D[row]==0):
                    number_of_comb[next_id]+=prev_number_of_comb[prev_id]

    if row==M-1:  
        for prev_id in range(len(transfer_matrix_end)):
            if transfer_matrix_end[prev_id]:
                for next_id,next_comb in transfer_matrix_end[prev_id]:
                    if (next_comb&T[M-1]==0)and(~next_comb&D[M-1]==0):
                        number_of_comb[next_id]+=prev_number_of_comb[prev_id]

  final_sum=0
  for end_id in end_labels:
    final_sum+=number_of_comb[end_id]
  print final_sum

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_SIZE 123455
typedef struct _node{
  int mask;
  int group;
  int r1;
  int r2;
  long long c;
  struct _node *next;
} node;
void insert(node **hash,int m,int g,int r1,int r2,long long c);
long long find(node **hash,int m,int g,int r1,int r2);
int hash_f(int m,int g,int r1,int r2);
long long solve(int l,int m,int g,int r1,int r2,int all);
int count(int i);
char table[8][9];
int N,M,T[8]={0},D[8]={0},dp[256][256],dl[256]={0};
node *hash[8][HASH_SIZE]={0};

int main(){
  int K,i,j,k;
  scanf("%d%d%d",&N,&M,&K);
  for(i=0;i<N;i++)
    scanf("%s",&table[i][0]);
  for(i=0;i<N;i++)
    for(j=0;j<M;j++)
      if(table[i][j]=='T')
        T[i]|=(1<<j);
      else if(table[i][j]=='D')
        D[i]|=(1<<j);
  for(i=0;i<(1<<M);i++)
    for(j=0;j<(1<<M);j++){
      for(k=1;k<M;k++)
        if((i&(1<<k))==((i&(1<<(k-1)))<<1)&&(i&(1<<k))==(j&(1<<k))&&(i&(1<<k))==((j&(1<<(k-1)))<<1))
          break;
      if(k==M)
        dp[i][dl[i]++]=j;
    }
  printf("%lld",solve(N,0,0,-K,K,0));
  return 0;
}
void insert(node **hash,int m,int g,int r1,int r2,long long c){
  int bucket=hash_f(m,g,r1,r2)%HASH_SIZE;
  node *t=hash[bucket];
  t=(node*)malloc(sizeof(node));
  t->mask=m;
  t->group=g;
  t->r1=r1;
  t->r2=r2;
  t->c=c;
  t->next=hash[bucket];
  hash[bucket]=t;
  return;
}
long long find(node **hash,int m,int g,int r1,int r2){
  int bucket=hash_f(m,g,r1,r2)%HASH_SIZE;
  node *t=hash[bucket];
  while(t){
    if(t->mask==m && t->group==g && t->r1==r1 && t->r2==r2)
      return t->c;
    t=t->next;
  }
  return -1;
}
int hash_f(int m,int g,int r1,int r2){
  return m+g*256+(r1+64)*256+r2+64;
}
long long solve(int l,int m,int g,int r1,int r2,int all){
  int i,j,k,G,ct,cg,mtg,mgg,diff,temp,temp2,tm[8],gm[8],ts,gs,group[8],group2[8],tma[4],gma[4],tmm[4],gmm[4];
  long long t;
  if(all){
    if(!l){
      if(g || r1>0 || r2<0)
        return 0;
      return 1;
    }
    if(M>1)
      return 0;
    if(m){
      if(D[l-1])
        return 0;
      return solve(l-1,m,g,r1-1,r2-1,all);
    }
    else{
      if(T[l-1])
        return 0;
      return solve(l-1,m,g,r1+1,r2+1,all);
    }
  }
  if(r1>l*M || r2<-l*M)
    return 0;
  if(r2>l*M)
    r2=l*M;
  if(r1<-l*M)
    r1=-l*M;
  if(l!=N && l){
    t=find(&hash[l][0],m,g,r1,r2);
    if(t!=-1)
      return t;
  }
  else if(l==N){
    for(i=t=0;i<(1<<M);i++){
      if((D[l-1]&i) || (T[l-1]&(~i)))
        continue;
      diff=2*count(i)-M;
      for(j=ts=gs=0;j<M;j++)
        if(j && (i&(1<<j))==((i&(1<<(j-1)))<<1))
          group[j]=group[j-1];
        else{
          if(i&(1<<j))
            group[j]=ts++;
          else
            group[j]=gs++;
        }
      for(j=temp2=0,ts=1;j<M;j++,ts*=4)
        temp2+=group[j]*ts;
      t+=solve(l-1,i,temp2,r1-diff,r2-diff,0);
    }
    return t;
  }
  if(l){
    G=g;
    mtg=mgg=0;
    for(j=0;j<M;g/=4,j++){
      group[j]=g%4;
      if(m&(1<<j)){
        if(group[j]>mtg)
          mtg=group[j];
      }
      else{
        if(group[j]>mgg)
          mgg=group[j];
      }
    }
    for(i=t=0;i<dl[m];i++){
      if((D[l-1]&dp[m][i]) || (T[l-1]&(~dp[m][i])))
        continue;
      temp2=all=ct=cg=0;
      diff=2*count(dp[m][i])-M;
      memset(tm,-1,sizeof(tm));
      memset(gm,-1,sizeof(gm));
      memset(tma,0,sizeof(tma));
      memset(gma,0,sizeof(gma));
      memset(tmm,-1,sizeof(tma));
      memset(gmm,-1,sizeof(gma));
      for(j=0,ts=gs=4;j<M;j++)
        if(j && (dp[m][i]&(1<<j))==((dp[m][i]&(1<<(j-1)))<<1))
          group2[j]=group2[j-1];
        else{
          if(dp[m][i]&(1<<j))
            group2[j]=ts++;
          else
            group2[j]=gs++;
        }
      for(j=0;j<M;j++)
        if((dp[m][i]&(1<<j))==(m&(1<<j))){
          if(m&(1<<j)){
            if(tmm[group[j]]==-1 && group2[j]>=4){
              tmm[group[j]]=group[j];
              temp=group2[j];
              for(k=0;k<M;k++)
                if(group2[k]==temp && ((dp[m][i]&(1<<k))>>k)==((m&(1<<j))>>j))
                  group2[k]=group[j];
            }
            else if(tmm[group[j]]==-1)
              tmm[group[j]]=group2[j];
            else if(tmm[group[j]]!=-1 && group2[j]>=4){
              temp=group2[j];
              for(k=0;k<M;k++)
                if(group2[k]==temp && ((dp[m][i]&(1<<k))>>k)==((m&(1<<j))>>j))
                  group2[k]=tmm[group[j]];
            }
            else if(tmm[group[j]]!=-1 && tmm[group[j]]!=group2[j]){
              temp=tmm[group[j]];
              tmm[group[j]]=group2[j];
              for(k=0;k<M;k++)
                if(group2[k]==temp && ((dp[m][i]&(1<<k))>>k)==((m&(1<<j))>>j))
                  group2[k]=group2[j];
            }
          }
          else{
            if(gmm[group[j]]==-1 && group2[j]>=4){
              gmm[group[j]]=group[j];
              temp=group2[j];
              for(k=0;k<M;k++)
                if(group2[k]==temp && ((dp[m][i]&(1<<k))>>k)==((m&(1<<j))>>j))
                  group2[k]=group[j];
            }
            else if(gmm[group[j]]==-1)
              gmm[group[j]]=group2[j];
            else if(gmm[group[j]]!=-1 && group2[j]>=4){
              temp=group2[j];
              for(k=0;k<M;k++)
                if(group2[k]==temp && ((dp[m][i]&(1<<k))>>k)==((m&(1<<j))>>j))
                  group2[k]=gmm[group[j]];
            }
            else if(gmm[group[j]]!=-1 && gmm[group[j]]!=group2[j]){
              temp=gmm[group[j]];
              gmm[group[j]]=group2[j];
              for(k=0;k<M;k++)
                if(group2[k]==temp && ((dp[m][i]&(1<<k))>>k)==((m&(1<<j))>>j))
                  group2[k]=group2[j];
            }
          }
        }
      for(j=ts=gs=0;j<M;j++)
        if(dp[m][i]&(1<<j))
          if(tm[group2[j]]==-1){
            tm[group2[j]]=ts++;
            group2[j]=ts-1;
          }
          else
            group2[j]=tm[group2[j]];
        else
          if(gm[group2[j]]==-1){
            gm[group2[j]]=gs++;
            group2[j]=gs-1;
          }
          else
            group2[j]=gm[group2[j]];
      for(j=0;j<M;j++)
        if(m&(1<<j)){
          if((m&(1<<j))==(dp[m][i]&(1<<j)))
            tma[group[j]]=1;
        }
        else{
          if((m&(1<<j))==(dp[m][i]&(1<<j)))
            gma[group[j]]=1;
        }
      for(j=0;j<M;j++)
        if(m&(1<<j)){
          if(!tma[group[j]]){
            if(dp[m][i])
              temp2=1;
            else
              all=1;
          }
        }
        else{
          if(!gma[group[j]]){
            if(dp[m][i]!=((1<<M)-1))
              temp2=1;
            else
              all=1;
          }
        }
      for(j=0;j<=mtg;j++){
        if(!tma[j])
          ct++;
      }
      for(j=0;j<=mgg;j++){
        if(!gma[j])
          cg++;
      }
      if(ct>1 || cg>1 || temp2)
        continue;
      for(j=temp=0,ts=1;j<M;j++,ts*=4)
        temp+=group2[j]*ts;
      t+=solve(l-1,dp[m][i],temp,r1-diff,r2-diff,all);
    }
    insert(&hash[l][0],m,G,r1,r2,t);
    return t;
  }
  if(g || r1>0 || r2<0)
    return 0;
  return 1;
}
int count(int i){
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}