#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 2005;
const int MOD = 111539786;

int n, k, nodes = 0;
int trie[N][2], fail[N], dp[2][N];
bool bad[N];

void insert(string s) {
    int u = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        int c = s[i] - '0';
        if (!trie[u][c]) trie[u][c] = ++nodes;
        u = trie[u][c];
    }
    bad[u] = true;
}

void build() {
    queue<int> q;
    for (int c = 0; c < 2; c++)
        if (trie[0][c]) q.push(trie[0][c]);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int c = 0; c < 2; c++) {
            if (trie[u][c]) {
                fail[trie[u][c]] = trie[fail[u]][c];
                bad[trie[u][c]] |= bad[fail[trie[u][c]]];
                q.push(trie[u][c]);
            } else trie[u][c] = trie[fail[u]][c];
        }
    }
}

void solve() {
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        string s; cin >> s;
        insert(s);
    }
    build();
    int cur = 0;
    dp[cur][0] = 1;
    for (int i = 0; i < n; i++)  {
        int nxt = cur ^ 1;
        memset(dp[nxt], 0, sizeof dp[nxt]);
        for (int u = 0; u <= nodes; u++) {
            if (dp[cur][u] == 0) continue;
            for (int c = 0; c < 2; c++) {
                int v = trie[u][c];
                if (!bad[v]) {
                    dp[nxt][v] += dp[cur][u];
                    if (dp[nxt][v] >= MOD) dp[nxt][v] -= MOD;
                }
            }
        }
        cur = nxt;
    }
    int ans = 0;
    for (int u = 0; u <= nodes; u++) {
        ans += dp[cur][u];
        if (ans >= MOD) ans -= MOD;
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    #define TASK "DNASEQ"
    if (fopen(TASK".INP", "r")) {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    int tests = 1; // cin >> tests;
    while (tests--) solve();

    #ifndef LOCAL
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
    
    return 0;
}