#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define debug printf
using namespace std;
typedef pair <int, int> PII;
typedef vector <int> VI;
typedef long long LL;
typedef long double ld;

const int MN = 150, mod = 1000000007; //jak tle to MN = 110

struct matrix
{
	LL V[MN][MN];
	matrix(LL prz = 1LL)
	{
		for(int i = 0; i < MN; ++i)
			for(int j = 0; j < MN; ++j)
				V[i][j] = 0LL;
		for(int i = 0; i < MN; ++i)
			V[i][i] = prz;
	}
	matrix operator*(matrix & m)
	{
		matrix wyn(0LL);
		for(int i = 0; i < MN; ++i)
			for(int j = 0; j < MN; ++j)
				for(int k = 0; k < MN; ++k)
				{
					wyn.V[i][j] += V[i][k] * m.V[k][j];
					wyn.V[i][j] %= mod;
				}
		return wyn;
	}
	matrix operator^(LL wyk)
	{
		matrix wyn(1LL), tmp = (*this);
		while(wyk)
		{
			if(wyk & 1LL)
				wyn = wyn * tmp;
			tmp = tmp * tmp;
			wyk >>= 1;
		}
		return wyn;
	}
	void wypisz()
	{
		for(int i = 0; i < MN; ++i)
		{
			for(int j = 0; j < MN; ++j)
				printf("%lld ", V[i][j]);
			printf("\n");
		}
	}
};

int kraw[MN][MN];
map < string, PII > mapa;
int node[MN][MN], used[MN][MN];
string S[MN];

int N;

PII dupa = {-1, -1};

void dfs(int p, int nr)
{
	used[p][nr] = 1;
	string cur = S[nr].substr(0, p); //sprawdz jak dokadnie to dziala xD
	int s = cur.size();
	cur += '+';
	node[p][nr] = ++N;
	int from = node[p][nr];
	vector < PII > raki;
	for(char c = 'a'; c <= 'z'; ++c)
	{
		cur[s] = c;
		PII naj = {0, 0};
		for(int j = 1; j <= s + 1; ++j)
		{
			PII kto = mapa[cur.substr(s + 1 - j, j)];
			if(kto == dupa)
			{
				naj = kto;
				break;
			}
			else if(kto.fi > 0)
			{
				naj = kto;
			}
		}
		if(naj.fi != -1)
		{
			if(!used[naj.fi][naj.se])
				dfs(naj.fi, naj.se);
			int to = node[naj.fi][naj.se];
			kraw[from][to]++;
		}
	}
}

int main ()
{
	ios_base::sync_with_stdio(false);
	int n, q;
	//wypierdol takie S, ze pewne S' to jego prefiks!
	//nie trzeba rego wypierdala na 99%, ale no, moze mozna xD wyjebane jajca na razie
	cin >> n >> q;
	for(int i = 1; i <= q; ++i)
	{
		int xd;
		cin >> xd >> S[i];
	}
	for(int i = 1; i <= q; ++i)
	{
		int l = S[i].length();
		for(int j = 1; j <= l; ++j)
		{
			string cur = S[i].substr(0, j);
			if(mapa[cur] != dupa)
				mapa[cur] = {j, i};
		}
		mapa[S[i]] = dupa;
	}
	dfs(0, 0);
	int s = N + 1, e = N + 2;
	kraw[s][1] = 1;
	for(int i = 1; i <= N; ++i)
		kraw[i][e] = 1;
	N += 2;
	n += 2;
	matrix A(0LL);
	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= N; ++j)
			A.V[i][j] = kraw[i][j];
	//A.wypisz();
	A = A^n;
	//A.wypisz();
	cout << A.V[s][e];
		
}