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

#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), " "

const int A = 26;
const int NONE = -1;
const int root = 0;
const char a = 'a';

struct node
{
	int down[A];
	int jump;
	char letter;
	int up;
	int over;
	node()
	{
		for(int i = 0; i < A; ++i)
			down[i] = NONE;
			
		letter = NONE;
		over = 0;
		up = NONE;		
	}
};

using Trie = vector<node>;

Trie make_trie()
{
	return vector<node> ({node()});
}

void insert(Trie &trie, string &s)
{
	int pos = 0;
	
	for(auto it:s)
	{
		//debug(s, int(it), int(a), int('a'));
	
		if(trie[pos].down[it-a] == NONE)
		{
			trie[pos].down[it-a] = trie.size();
			trie.push_back(node());
			trie.back().up = pos;
			pos = trie.size() - 1;
		}
		else
			pos = trie[pos].down[it-a];
		
		trie[pos].letter = it;
	}
	
	trie[pos].over++;
}

void make_jumps(Trie &trie)
{
	queue<int> kol;
	kol.push(0);
	
	while(kol.size())
	{
		int pos = kol.front();
		kol.pop();
		
		
		//debug(pos, trie[pos].up, root);
		
		if(pos == root)
		{
			//debug(1, pos);
			trie[pos].jump = root;
		}
		else if(trie[pos].up == root)
		{
			//debug(2, pos);
			trie[pos].jump = root;//, debug(pos);
		}
		else
		{
			//debug(3, pos);
			int alt = trie[trie[pos].up].jump;
			
			while(trie[alt].down[trie[pos].letter - a] == NONE && alt != root)
				alt = trie[alt].jump;
				
			if(trie[alt].down[trie[pos].letter - a] == NONE)
				trie[pos].jump = root;
			else
				trie[pos].jump = trie[alt].down[trie[pos].letter - a];
			
			trie[pos].over += trie[trie[pos].jump].over;
		}
		
		assert(trie[pos].jump != NONE);
		
		for(int i = 0; i < A; ++i)
		{
			if(trie[pos].down[i] != NONE)
				kol.push(trie[pos].down[i]);
		}
	}
}

#define int ll
const int mod = 1e9+7;
const int N = 107;

int n, q;

struct mat
{
	int m[N][N];
	
	mat()
	{
		for(int i = 0; i < N; ++i)
		{
			for(int j = 0; j < N; ++j)
				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] += A.m[i][k]*B.m[k][j];
				C.m[i][j] %= mod;
			}
		}
	}
	
	return C;
}

mat fpow(mat A, int b)
{
	mat res;
	
	for(int i = 0; i < N; ++i)
	{
		res.m[i][i] = 1;
	}
	
	while(b)
	{
		if(b&1)
			res = res*A;
			
		A = A*A;
		b /= 2;
	}
	
	return res;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	const int nax = 1e9;
	int sum_len = 0;
	
	cin >> n >> q;
	
	assert(1<=n && n<=nax);
	assert(1<=q && q<=100);
	
	Trie T = make_trie();
	
	while(q--)
	{
		int l;
		string s;
		cin >> l >> s;
		assert(l==siz(s));
		assert(1<=l && l<=100);
		sum_len += l;
		insert(T, s);
	}
	
	assert(sum_len <= 100);
	
	make_jumps(T);
	
	int k = T.size();
	
	assert(k<=101);
	
	mat X;
	
	//debug(T[1].up, T[1].jump);
	
	for(int i = 0; i < k; ++i)
	{
		for(int l = 0; l < A; ++l)
		{
			int pos = i;
			
			while(pos != root && T[pos].down[l] == NONE)
				pos = T[pos].jump;//, debug(pos);
			
			pos = T[pos].down[l];
			
			if(pos == NONE)
				pos = root;
				
			if(!T[pos].over)
				X.m[i][pos]++;
		}
	}
	
	X = fpow(X, n);
	
	int ans = 0;
	
	for(int i = 0; i < k; ++i)
	{
		if(T[i].over)
			assert(!X.m[0][i]);
	
		ans += X.m[0][i];
		ans %= mod;
	}
	
	ans %= mod;
	ans += mod;
	ans %= mod;
	
	cout << ans << endl;
}