Language: C++

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) container.begin(), container.end()
#define RALL(container) container.rbegin(), container.rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


int N, M, L;

// O(n^2)で<=nのコンビネーションを作る
// (パスカルの三角形)
ll C[1010][1010];

void make_C(){
    memset(C, 0, (int)sizeof(C));    
    for(int i = 0; i < 1010; i++){
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j++) C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
}
vector<vi> seqs;
int check(const vi &hand, vector<vi> seqs){
	if(seqs.empty()) return 0;
	vi tar = seqs.back();
	int res = 0;
	REP(i, seqs.size()) res += accumulate(ALL(seqs[i]), 0);
	seqs.pop_back();
	REP(i, hand.size()){
		if(i && hand[i-1] == hand[i]) continue;
		vi next = hand;
		int base = hand[i];
		int f = 0;
		REP(d, tar.size()){
			REP(i, tar[d]){
				auto it = find(ALL(next), base + d);
				if(it == next.end()){
					f++;
				}else next.erase(it);
			}
		}
		if(res > f) res = min(res, f + check(next, seqs));
		if(res == 0) return 0;
	}
	return res;
}

vector<int> compress(const vi &hand, const int tail){
	if(hand.empty()) return vector<int>();
	vector<int> res;
	int base = -10;
	REP(i, (int)hand.size() - 1){
		res.push_back(min(2, hand[i+1] - hand[i]));
	}
	res.push_back(tail);
	return res;
}

map<vector<int>, ll> memo;
ll enumerate(vi &hand, int tail){
	if(count(ALL(hand), tail) > M) return 0;
	
	vector<int> state = compress(hand, tail);
	auto memop = memo.find(state);
	if(memop != memo.end()) return memop->second;
	
	int need = check(hand, seqs);
//	cout << hand << ": " << need << endl;
	if(need == 0){
		map<int, int> dist;
		FOR(it, hand) dist[*it] ++;
		ll res = 1;
		FOR(it, dist) res *= C[M][it->second];
		ll rest = L - hand.size();
		ll allr = M*(N-tail);
		if(rest){
			hand.push_back(tail);
			res = res * C[allr][rest] + enumerate(hand, tail);
			hand.pop_back();
		}
//		cout << hand << ": " << res << endl;
		return memo[state] = res;
	}else if(need > L - hand.size()) return memo[state] = 0;
	if(hand.size() == L){
		return 0;
	}
	ll res = 0;
	hand.push_back(tail);
	for(int i=tail;i<=N;i++){
		hand.back() = i;
		res += enumerate(hand, i);
	}
	hand.pop_back();
	return memo[state] = res;
}


main(){
	make_C();
	ios::sync_with_stdio(false);
	while(cin >> M >> N >> L, N){
		seqs = vector<vi>(3);
		int ast=3;
		REP(i, L){
			string s;
			cin >> s;
			if(s[0] != '*'){
				int d = s.size() - 1;
				int t = s[0] - 'a';
				if(seqs[t].size() <= d) seqs[t].resize(d+1);
				seqs[t][d] ++;
			}
		}
		RREP(i, seqs.size()){
			if(accumulate(ALL(seqs[i]), 0) <= 1) seqs.erase(seqs.begin() + i);
		}
//		cout << seqs << endl;
		vi hand;
//		printf("%lld / %lld\n", enumerate(hand, 1), C[N*M][L]);
		printf("%.10f\n", enumerate(hand, 1) / (double)C[N*M][L]);
		memo.clear();
	}
	return 0;
}

Compiler output:
a.cc: In function 'int check(const vi&, std::vector<std::vector<int> >)':
a.cc:74:36: error: 'accumulate' was not declared in this scope
   74 |         REP(i, seqs.size()) res += accumulate(ALL(seqs[i]), 0);
      |                                    ^~~~~~~~~~
a.cc: At global scope:
a.cc:145:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  145 | main(){
      | ^~~~
a.cc: In function 'int main()':
a.cc:162:28: error: 'accumulate' was not declared in this scope
  162 |                         if(accumulate(ALL(seqs[i]), 0) <= 1) seqs.erase(seqs.begin() + i);
      |                            ^~~~~~~~~~