#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

const int M = 1000000007;

const int Qmax = 101;

struct matrix {
    int szamok[Qmax][Qmax] = {};
    const int* operator [](int x) const {
        return szamok[x];
    }
    int* operator [](int x) {
        return szamok[x];
    }
};

matrix operator *(const matrix& A, const matrix& B) {
    matrix C;
    for(int i = 0; i < Qmax; i++)
        for(int j = 0; j < Qmax; j++)
            for(int k = 0; k < Qmax; k++) {
                C[i][k] += ((ll)A[i][j] * B[j][k])%M;
                C[i][k] %= M;
            }
    return C;
}

matrix mpow(matrix A, int N) {
    matrix B;
    for(int i = 0; i < Qmax; i++) {
        B[i][i] = 1;
    }
    while(N) {
        if(N & 1) {
            B = B * A;
        }
        A = A * A;
        N /= 2;
    }
    return B;
}

struct szofa {
    szofa* hova[26] = {};
    szofa* honnan = nullptr;
    szofa* kov0(char c) {
        return hova[c - 'a'];
    }
    szofa* kov(char c) {
        szofa*& s = hova[c-'a'];
        if(!s) {
            s = new szofa;
            s->ch = c-'a';
            s->honnan = this;
        }
        return s;
    }
    int ch;
    szofa* e = nullptr;
    bool szv = false;
    int id;
};

szofa* kov(szofa* e0, int x, szofa* gy) {
    while(e0 && !e0->hova[x]) {
        e0 = e0->e;
    }
    if(e0) {
        return e0->hova[x];
    }
    else {
        return gy;
    }
}

void szamol1(szofa* sz, szofa* gyoker) {
    szofa* e0 = sz->honnan->e;
    sz->e = kov(e0, sz->ch, gyoker);
}

int main()
{
    int N, Q;
    cin >> N >> Q;
    szofa szf;
    for(int i = 0; i < Q; i++) {
        int _;
        cin >> _;
        string s;
        cin >> s;
        szofa* cs = &szf;
        for(char c : s) {
            cs = cs->kov(c);
        }
        cs->szv = true;
    }
    vector<szofa*> v;
    vector<szofa*> v1 = {&szf};
    while(v1.size()) {
        vector<szofa*> v2;
        for(szofa* cs : v1) {
            for(szofa* cs2 : cs->hova) {
                if(cs2) {
                    v2.push_back(cs2);
                    v.push_back(cs2);
                }
            }
        }
        swap(v1, v2);
    }
    for(szofa* sz : v) {
        szamol1(sz, &szf);
        sz->szv |= sz->e->szv;
    };
    v.insert(v.begin(), &szf);
    int X = 0;
    for(szofa* sz : v) {
        sz->id = X++;
    }
    matrix m;
    for(int i = 0; i < X; i++) {
        for(int j = 0; j < 26; j++) {
            szofa* cs = kov(v[i], j, & szf);
            if(!cs->szv)
            m[i][cs->id]++;
        }
    }
    matrix A = mpow(m, N);
    int er = 0;
    for(int i = 0; i < Qmax; i++) {
        er += A[0][i];
        er %= M;
    }
    cout << er << "\n";
}