#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <functional>
using namespace std;
long long power[20];
class TCPhoneHome {
public:
	long long validNumbers(int n, vector<string>S) {
		power[0] = 1; for (int i = 1; i < 19; i++)power[i] = power[i - 1] * 10LL;
		long long ret = power[n];
		for (int i = 0; i < S.size(); i++) {
			bool OK = false;
			for (int j = 0; j < S.size(); j++) {
				if (i == j)continue;
				if (S[i].size() < S[j].size())continue;
				if (S[i].substr(0, S[j].size()) == S[j])OK = true;
			}
			if (OK == false)ret -= power[n - S[i].size()];
		}
		return ret;
	}
};