#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;

const int SIGMA = 26;
const int MAXBUF = 103;

inline int alpha(char c) {return c-'a';}

struct node {
    node* prefix, *next[SIGMA];
    const char *end;
    node* accept;
    node* get_accept() {return end ? this : accept;}
    int num = 0;
    void evaluate(int a, queue<node*> Q) {
        if(next[a]) {
            next[a]->prefix = prefix->next[a];
            next[a]->accept = next[a]->prefix->get_accept();
            Q.push(next[a]);     
        }
        else next[a] = prefix->next[a];
    }
};

node buf[MAXBUF];
int bufc;

node* get_node() {
    for(int a=0;a<SIGMA;a++) buf[bufc].next[a] = 0;
    buf[bufc].num = bufc;
    buf[bufc].end = 0;
    buf[bufc].accept = 0;
    return buf+bufc++;
}

void add_str(node* root, const char *str) {
    for(int i=0; str[i]; ++i) {
        int a = alpha(str[i]);
        if(!root->next[a]) {
            root->next[a] = get_node();
        }
        root = root->next[a];
    }
    root->end = str;
}

void evaluate(node* root) {
    root->prefix = get_node();
    for(int a=0;a<SIGMA;a++)
        root->prefix->next[a] = root;

    queue<node*> Q;
    Q.push(root);
    
    while(!Q.empty()) {
        node* cur = Q.front(); Q.pop();
        for(int a=0;a<SIGMA;a++)
            cur->evaluate(a,Q);
    }
}

void addEdge(node* cur, node* root, int a) {
    node* cp = cur;
    while(cur->next[a] == NULL) {
        cur = cur->prefix;
        if(cur == NULL) {
            cur = root;
            break;
        }

    }
    cp->next[a] = cur->next[a];
}

int visited[MAXBUF];

vector<vector<ll> > matrix(MAXBUF,vector<ll>(MAXBUF));

void dfs(node* root, node* roott) {
    if(root->end != NULL)
        return;
    visited[root->num] = 1;
    for(int i=0;i<SIGMA;i++) {
        addEdge(root,roott,i);
        if(root->next[i]->end != NULL)
            continue;
        matrix[root->num][root->next[i]->num]++;
        if(visited[root->next[i]->num] == 0) {
            dfs(root->next[i],roott);
        }
    }
}


const ll MOD = 1e9+7;
vector<vector<ll> > mul(vector<vector<ll> > a, vector<vector<ll> > b) {
    vector<vector<ll> > c(a.size(),vector<ll>(a.size()));
    for(int i=0;i<a.size();i++)
        for(int j=0;j<a.size();j++)
            for(int k=0;k<a.size();k++)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
    return c;
}

vector<vector<ll> > fme(vector<vector<ll> > a, ll k) {
    if(k == 0) {
        for(int i=0;i<a.size();i++)
            for(int j=0;j<a.size();j++)
                a[i][j] = (i==j ? 1 : 0);
        return a;
    }
    if(k%2 == 1) {
        return mul(fme(a,k-1),a);
    }
    auto tmp = fme(a,k/2);
    return mul(tmp,tmp);
}

int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    vector<string> vect(m);
    for(int i=0;i<m;i++) {
        int a;
        cin >> a >> vect[i];
    }
    sort(vect.begin(),vect.end());
    vect.erase(unique(vect.begin(),vect.end()),vect.end());
    sort(vect.begin(),vect.end(),[](const string&a, const string&b) {if(a.size() == b.size()) return a<b; return a.size() < b.size(); });

    node* root = get_node();
    int adds = 0;
    for(int i=0;i<vect.size();i++) {
        bool bad = false;
        for(int j=0;j<i;j++) {
            if(vect[i].find(vect[j]) != vect[i].npos) {
                bad = true;
                break;
            }
        }
        if(!bad) {
            add_str(root,vect[i].c_str());
            adds++;
        }
    }
    cerr<<adds<<endl;
    evaluate(root);
    dfs(root,root);

    auto res = fme(matrix,n);
    ll v = 0;
    for(int i=0;i<res.size();i++)
        v = (v+res[0][i])%MOD;
    cout<<v<<endl;
   
}