#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;

ll power_10(ll exp) {
    ll res = 1;
    for(ll i = 0; i < exp; i++) {
        res *= 10;
    }
    return res;
}
int main() {
    ios_base::sync_with_stdio(false);
    ll N, P;
    cin >> N >> P;
    vector<string> prefixes(P);
    set<string> st;
    for(int i = 0; i < P; i++) {
        cin >> prefixes[i];
        st.insert(prefixes[i]);
    }
    vector<string> minimal;

    for(int i = 0; i < P; i++) {
        string pre = "";
        bool ok = false;
        for(int j = 0; j < prefixes[i].length() - 1; j++) {
            pre += prefixes[i][j];
            if(st.count(pre)) {
                ok = true;
                break;
            }
        }
        if(!ok) {
            minimal.push_back(prefixes[i]);
        }
    }

    ll total_numbers = power_10(N);
    ll half = (N + 1) / 2;
    ll palindromes = power_10(half);

    ll numbers_forbidden = 0, palindromes_forbidden = 0;
    for(string p: minimal) {
        ll L = p.length();
        numbers_forbidden += power_10(N - L);
        if(L <= half) {
            palindromes_forbidden += power_10(half - L);
        }
        else {
            string tmp(N, '0');
            for(int j = 0; j < half; j++) {
                tmp[j] = p[j];
            }
            for(int j = half; j < N; j++) {
                tmp[j] = tmp[N - 1 - j];
            }
            if(tmp.compare(0, L, p) == 0) {
                palindromes_forbidden += 1;
            }




        }
    }


    cout << (total_numbers - palindromes - numbers_forbidden + palindromes_forbidden) << endl;
    return 0;
}