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

constexpr int alpha = 26;
constexpr char first = 'a';

struct AhoCorasick {
	struct Node {
		int back, next[alpha], start = -1, end = -1;
		Node(int v) { fill_n(next, alpha, v); }
	};
	vector<Node> N;
	vector<int> backp;
	void insert(const string& s, int j) {
		int n = 0;
		for (char c : s) {
			int& m = N[n].next[c - first];
			if(m == -1) {n=m=N.size();N.emplace_back(-1);}
			else n = m;
		}
		if (N[n].end == -1) N[n].start = j;
		backp.push_back(N[n].end);
		N[n].end = j;
	}
	AhoCorasick(const vector<string>& pat) {
		N.emplace_back(-1);
		for(unsigned i=0;i<pat.size();++i) {
			insert(pat[i], i);
		}
		N[0].back = N.size();
		N.emplace_back(0);
		queue<int> q;
		for(q.push(0);!q.empty();q.pop()) {
			int n = q.front(), prev = N[n].back;
			for (int i=0; i < alpha; ++i) {
				int &ed = N[n].next[i], y = N[prev].next[i];
				if (ed == -1) ed = y;
				else {
					N[ed].back = y;
					(N[ed].end == -1 ? N[ed].end : backp[N[ed].start]) = N[y].end;
					q.push(ed);
				}
			}
		}
	}
};

using Matrix = vector<vector<int>>;

using ll = long long;
constexpr ll MOD = 1000000007;

void check(const Matrix& ngh) {
	const int sz = ngh.size();
	for (int i=0;i<sz;++i) for (int j=0;j<sz;++j) {
		assert(ngh[i][j] >= 0);
		assert(ngh[i][j] < MOD);
	}
}

Matrix FromAho(const AhoCorasick& aho) {
	assert(aho.N[0].end == -1);
	const int sz = aho.N.size();
	Matrix ret(sz, vector<int>(sz));
	for (int i = 0; i < sz; ++i) {
		if (aho.N[i].end != -1) continue;
		for (int j = 0; j < alpha; ++j) {
			const int k = aho.N[i].next[j];
			if (aho.N[k].end == -1) ret[i][k]++;
		}
	}
	check(ret);
	return ret;
}

Matrix mul(const Matrix& a, const Matrix& b) {
	check(a); check(b);
	const int sz = a.size();
	Matrix c(sz, vector<int>(sz));
	for (int i=0;i<sz;++i)
	for (int k=0;k<sz;++k)
	for (int j=0;j<sz;++j) {
		assert(c[i][j] >= 0);
		assert(c[i][j] < MOD);
		c[i][j] = ll(c[i][j]) + ll(a[i][k]) * ll(b[k][j]) % MOD;
	}
	check(c);
	return c;
}

Matrix fpw(Matrix a, int n) {
	const int sz = a.size();
	Matrix ret(sz, vector<int>(sz, 0));
	for (int i=0;i<sz;++i) ret[i][i] = 1;
	while (n) {
		if (n & 1)
			ret = mul(ret, a);
		a = mul(a, a);
		n /= 2;
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,q;
	cin >> n >> q;
	vector<string> bad;
	while (q--) {
		bad.emplace_back();
		int x;
		cin >> x >> bad.back();
	}
	/*
	Matrix x = FromAho(AhoCorasick(bad));
	const int sz0 = x.size();
	cerr << sz0 << endl;
	for (int i=0;i<sz0;++i) {
		for (int j=0;j<sz0;++j) cerr << x[i][j] << ' ';
		cerr << endl;
	}
	*/
	Matrix ngh = fpw(FromAho(AhoCorasick(bad)), n);
	check(ngh);
	long long ans = 0;
	const int sz = ngh.size();
	for (int i = 0; i < sz; ++i)
		ans += ngh[0][i];
	cout << ans % MOD << '\n';
}