#include <bits/stdc++.h>
using namespace std;
#define int ll
#define LL long long
#define LD long double
#define PII pair<int, int>
#define VI vector<int>
#define VPII vector<PII>
#define f first
#define s second
#define MP make_pair
#define PB push_back
#define endl '\n'
#define SIZ(c) (int)(c).size()
#define ALL(c) (c).begin(), (c).end()
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, b, e) for (int i = (b); i <= (int)(e); i++)
#define FORD(i, b, e) for (int i = (b); i >= (int)(e); i--)
#define ll LL
#define st f
#define nd s
#define mp MP
#define pb PB
#define eb emplace_back
#define siz(c) SIZ(c)
const int inf = 1e9 + 7;
const LL INF = 1e18L + 7;

#define sim template<class n
sim, class s> ostream & operator << (ostream &p, pair<n, s> x)
{return p << "<" << x.f << ", " << x.s << ">";}
sim> auto operator << (ostream &p, n y) ->
typename enable_if<!is_same<n, string>::value, decltype(y.begin(), p)>::type
{int o = 0; p << "{"; for (auto c : y) {if (o++) p << ", "; p << c;} return p << "}";}
void dor() {cerr << "\n";}
sim, class...s> void dor(n p, s...y) {cerr << p << " "; dor(y...);}
sim, class s> void mini(n &p, s y) {if (p > y) p = y;}
sim, class s> void maxi(n &p, s y) {if (p < y) p = y;}

#ifdef DEB
#define debug(...) dor(__FUNCTION__, ":", __LINE__, ": ", __VA_ARGS__)
#else
#define debug(...)
#endif

#define I(x) #x " =", (x), " "

#include <sys/time.h>
timeval tv;

const int MXN = 1004;
const int A = 26;
int nxt[MXN][A];
int fat[MXN];
char fat2[MXN];
bool endd[MXN];
bool end2[MXN];
int suf[MXN];
PII best[MXN];
int root = 0;
#define free sakdjaskljflfj
int free = 1;

string read(int x)
	{
	string s;
	while(x != root)
		{
		s += fat2[x];
		x = fat[x];
		}
	reverse(ALL(s));
	return s;
	}




const int mod = 1000 * 1000 * 1000 + 7;
const int N = 127;

int n, q;

struct mat
{
	int m[N][N];
	
	mat()
	{
		REP(i, N)
			REP(j, N)
				m[i][j] = 0;
	}
};

mat operator * (mat A, mat B)
{
	mat C;
	
	for(int i = 0; i < N; ++i)
	{
		for(int j = 0; j < N; ++j)
		{
			for(int k = 0; k < N; ++k)
			{
				assert(0<=A.m[i][k] && A.m[i][k]<mod);
				assert(0<=B.m[k][j] && B.m[k][j]<mod);
			
				C.m[i][j] = (C.m[i][j] + A.m[i][k] * B.m[k][j]) % mod;
			}
		}
	}
	
	return C;
}

mat fpow(mat A, int n)
	{
	if(n == 0)assert(false);
	if(n == 1)return A;
	if(n % 2 == 0)
		return fpow(A*A, n/2);
	return fpow(A, n-1) * A;
	}

void dawid()
	{
	mat X;
	
	//debug(T[1].up, T[1].jump);
	
	for(int i = 0; i < free; ++i)
	{
		for(int l = 0; l < A; ++l)
		{
			int pos = i;
			
			while(pos != root && nxt[pos][l] == -1)
				pos = suf[pos];
				
//			debug(pos);
			
			pos = nxt[pos][l];
//			debug(pos, "tu");
			
			if(pos == -1)
				pos = root;
				
			if(!end2[pos])
				{
//				debug(i, pos);
				X.m[i][pos]++;
				}
			else
				{
//				debug(i, pos);
				}
		}
	}
	
	X = fpow(X, n);
	
	int ans = 0;
	
	for(int i = 0; i < free; ++i)
	{
		if(end2[i])
			assert(!X.m[0][i]);
	
		ans += X.m[0][i];
		ans %= mod;
	}
	
	ans %= mod;
	ans += mod;
	ans %= mod;
	
	cout << ans << endl;
	}

bool match(string s1, string s2)
	{
	assert(s1.size() >= s2.size());
	
	REP(i, (int)s1.size() - s2.size()+1)
		{
		bool ok = 1;
		REP(j, s2.size())
			{
			if(s2[j] != s1[i+j])ok = 0;
			}
		if(ok)return 1;
		}
	return 0;
	}

int32_t main()
{
	debug(mod);

	cin >> n >> q;
	
	REP(i, MXN)
		REP(j, A)
			nxt[i][j] = -1;
	
	vector<string> in;
	
	REP(i, q)
		{
		int l;
		string s;
		cin >> l >> s;
		assert(l == (int)s.size());


		reverse(ALL(s));		
		if(s.size() <= n)in.PB(s);
		}
		
		
	REP(i, in.size())
		{
		REP(j, in.size())
			{
			if(in[i].size() < in[j].size() || i == j)continue;
			if(match(in[i], in[j]))
				{
				in.erase(in.begin()+i);
				i--;
				break;
				}
			
			}
		}
		
	debug(in);
		
	
	for(auto s : in)
		{
		
		int act = root;
		REP(j, s.size())
			{
			if(nxt[act][s[j]-'a'] == -1)
				{
				nxt[act][s[j]-'a'] = free++;
				fat[free-1] = act;
				fat2[free-1] = s[j]-'a';
				}
			
			act = nxt[act][s[j]-'a'];
			}
		endd[act] = end2[act] = 1;
		}

	debug(free);


	REP(i, free)
		{
		string mine = read(i);
		
		REP(j, free)
			{
			if(j == i)continue;
			string theirs = read(j);
			
			if(theirs.size() >= mine.size())continue;
			
			bool ok = 1;
			REP(u, theirs.size())
				{
				if(theirs[theirs.size()-u-1] != mine[mine.size()-1-u])
					{
					ok = 0;
					break;
					}				
				}
			if(!ok)continue;
			end2[i] |= end2[j];
			if(best[i].f < (int)theirs.size())best[i] = MP((int)theirs.size(), j);
			}
		}

	REP(i, free)
		{
		suf[i] = best[i].s;
		
//		debug(i, suf[i], end2[i]);
		}


	dawid();
}