#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;
	}
};

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPGZ1bmN0aW9uYWw+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmxvbmcgbG9uZyBwb3dlclsyMF07CmNsYXNzIFRDUGhvbmVIb21lIHsKcHVibGljOgoJbG9uZyBsb25nIHZhbGlkTnVtYmVycyhpbnQgbiwgdmVjdG9yPHN0cmluZz5TKSB7CgkJcG93ZXJbMF0gPSAxOyBmb3IgKGludCBpID0gMTsgaSA8IDE5OyBpKyspcG93ZXJbaV0gPSBwb3dlcltpIC0gMV0gKiAxMExMOwoJCWxvbmcgbG9uZyByZXQgPSBwb3dlcltuXTsKCQlmb3IgKGludCBpID0gMDsgaSA8IFMuc2l6ZSgpOyBpKyspIHsKCQkJYm9vbCBPSyA9IGZhbHNlOwoJCQlmb3IgKGludCBqID0gMDsgaiA8IFMuc2l6ZSgpOyBqKyspIHsKCQkJCWlmIChpID09IGopY29udGludWU7CgkJCQlpZiAoU1tpXS5zaXplKCkgPCBTW2pdLnNpemUoKSljb250aW51ZTsKCQkJCWlmIChTW2ldLnN1YnN0cigwLCBTW2pdLnNpemUoKSkgPT0gU1tqXSlPSyA9IHRydWU7CgkJCX0KCQkJaWYgKE9LID09IGZhbHNlKXJldCAtPSBwb3dlcltuIC0gU1tpXS5zaXplKCldOwoJCX0KCQlyZXR1cm4gcmV0OwoJfQp9Ow==