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

#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<

#define pb push_back
#define x first
#define y second

#define LT <
#define GT >

typedef long long ll;
typedef long double lf;

const int MAXN = 150;
const int ALPHA = 26;

int V = 1;
int trie[MAXN][ALPHA + 10];
int fn[MAXN];
int flag[MAXN];
pair<int, int> dad[MAXN];
int dep[MAXN];

int node() {
  REP(i, ALPHA) trie[V][i] = 0;
  fn[V] = 0;
  return V++;
}

int insert(char *s) {
  int t = 0;
  for (; *s; ++s) {
    int c = (*s) - 'a';
    if (trie[t][c] == 0) trie[t][c] = node();
    t = trie[t][c];
    
    /*
    int nt = trie[t][c];
    dad[nt] = {t, c};
    dep[nt] = dep[t] + 1;
    */
  }
  return t;
}

/*
int try_aho(int t, int l) {
  if (l > dep[t]) return false;
  vector<int> path;
  path.reserve(l);
  REP(i, l) {
    path.push_back(dad[t].second);
    t = dad[t].first;
  }
  reverse(path.begin(), path.end());
  t = 0;
  for (int c : path) {
    if (trie[t][c] == 0) return -1;
    t = trie[t][c];
  }
  return t;
}
*/

void init_aho() {
  queue<int> Q;
  Q.push(0);
  
  while (!Q.empty()) {
    int t = Q.front(); Q.pop();

    REP(c, ALPHA) {
      int x = trie[t][c];
      if (x) {
        Q.push(x);

        if (t) {
          fn[x] = fn[t];
          while (fn[x] && trie[fn[x]][c] == 0) fn[x] = fn[fn[x]];
          if (trie[fn[x]][c]) fn[x] = trie[fn[x]][c];
        }
      }
    }
  }
}

int memo_next[MAXN][ALPHA];
int next(int t, int c) {
  if (trie[t][c] != 0) return trie[t][c];
  if (t == 0) return t;
  if (memo_next[t][c] != -1)
    return memo_next[t][c];
  return memo_next[t][c] = next(fn[t], c);
}

int memo_terminal[MAXN];
int terminal(int t) {
  if (t == 0) return 0;
  if (flag[t]) return 1;
  if (memo_terminal[t] != -1)
    return memo_terminal[t];
  return memo_terminal[t] = terminal(fn[t]); 
}

const int MOD = 1000000007;

struct Matrix {
  int a[MAXN][MAXN];
  int *operator[] (int r) { return a[r]; }

  Matrix(int x = 0) {
    memset(a, 0, sizeof a);
    if (x) REP(i, MAXN) a[i][i] = x;
  }
} const I(1);

Matrix operator * (Matrix A, Matrix B) {
  const ll mod2 = (ll)MOD * MOD;
  Matrix C;
  REP(i, MAXN) REP(j, MAXN) {
    ll w = 0;
    REP(k, MAXN) {
      w += (ll)A[i][k] * B[k][j];
      if (w >= mod2) w -= mod2;
    }
    C[i][j] = w % MOD;
  }
  return C;
}

Matrix operator ^ (Matrix A, ll b) {
  Matrix R = I;
  for (; b > 0; b /= 2) {
    if (b % 2) R = R*A;
    A = A*A;
  }
  return R;
}



int l, q;
char w[1000];

int main(void) {
  scanf("%d%d", &l, &q);
  REP(i, q) {
    int tmp;
    scanf("%d%s", &tmp, w);
    flag[insert(w)] = 1;
  }
  
  init_aho();
  
  memset(memo_next, -1, sizeof memo_next);
  memset(memo_terminal, -1, sizeof memo_terminal);

  Matrix mat;

  
  REP(t, V) {
    REP(c, ALPHA) {
      int nt = next(t, c);
      if (terminal(t) || terminal(nt))
        continue;
      mat[t][nt]++;
    }
  }

  
  /*
  REP(i, V) {
    REP(c, 3) {
      TRACE(i _ c _ fn[i] _ next(i, c));
    }
   cerr << endl; 
  }*/


  
  
  //TRACE(try_aho(4, 3));

  Matrix R = mat ^ l;

  int ans = 0;
  REP(i, V) {
	if (terminal(i)) continue;
    ans = (ans + R[0][i]) % MOD;
}
  printf("%d\n", ans);

  return 0;
}