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

typedef long long ll;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
  cout << vars << " = ";
  string delim = "";
  (..., (cout << delim << values, delim = ", "));
  cout << '\n';
}

template<int MOD>
struct ModInt {
    long long v;
    ModInt(long long _v = 0) {v = (-MOD < _v && _v < MOD) ? _v : _v % MOD; if (v < 0) v += MOD;}
    ModInt& operator += (const ModInt &other) {v += other.v; if (v >= MOD) v -= MOD; return *this;}
    ModInt& operator -= (const ModInt &other) {v -= other.v; if (v < 0) v += MOD; return *this;}
    ModInt& operator *= (const ModInt &other) {v = v * other.v % MOD; return *this;}
    ModInt& operator /= (const ModInt &other) {return *this *= inverse(other);}
    bool operator == (const ModInt &other) const {return v == other.v;}
    bool operator != (const ModInt &other) const {return v != other.v;}
    friend ModInt operator + (ModInt a, const ModInt &b) {return a += b;}
    friend ModInt operator - (ModInt a, const ModInt &b) {return a -= b;}
    friend ModInt operator * (ModInt a, const ModInt &b) {return a *= b;}
    friend ModInt operator / (ModInt a, const ModInt &b) {return a /= b;}
    friend ModInt operator - (const ModInt &a) {return 0 - a;}
    friend ModInt power(ModInt a, long long b) {ModInt ret(1); while (b > 0) {if (b & 1) ret *= a; a *= a; b >>= 1;} return ret;}
    friend ModInt inverse(ModInt a) {return power(a, MOD - 2);}
    friend istream& operator >> (istream &is, ModInt &m) {is >> m.v; m.v = (-MOD < m.v && m.v < MOD) ? m.v : m.v % MOD; if (m.v < 0) m.v += MOD; return is;}
    friend ostream& operator << (ostream &os, const ModInt &m) {return os << m.v;}
};
using M = ModInt<998244353>;

template<typename T>
vector<T> berlekampMassey(const vector<T> &s) {
  vector<T> c;
  vector<T> oldC;
  int f = -1;
  for (int i=0; i<(int)s.size(); i++) {
    T delta = s[i];
    for (int j=1; j<=(int)c.size(); j++)
      delta -= c[j-1] * s[i-j];
    if (delta == 0)
      continue;
    if (f == -1) {
      c.resize(i + 1);
      mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      for (T &x : c)
        x = rng();
      f = i;
    } else {
      vector<T> d = oldC;
      for (T &x : d)
        x = -x;
      d.insert(d.begin(), 1);
      T df1 = 0;
      for (int j=1; j<=(int)d.size(); j++)
        df1 += d[j-1] * s[f+1-j];
      assert(df1 != 0);
      T coef = delta / df1;
      for (T &x : d)
        x *= coef;
      vector<T> zeros(i - f - 1);
      zeros.insert(zeros.end(), d.begin(), d.end());
      d = zeros;
      vector<T> temp = c;
      c.resize(max(c.size(), d.size()));
      for (int j=0; j<(int)d.size(); j++)
        c[j] += d[j];
      if (i - (int) temp.size() > f - (int) oldC.size()) {
        oldC = temp;
        f = i;
      }
    }
  }
  return c;
}

template<typename T>
T solve(const vector<T> &c, const vector<T> &s, long long k) {
    int n = (int) c.size();
    assert(c.size() <= s.size());

    auto mul = [&] (const vector<T> &a, const vector<T> &b) -> vector<T> {
      vector<T> ret(a.size() + b.size() - 1);
      for (int i=0; i<(int)a.size(); i++)
        for (int j=0; j<(int)b.size(); j++)
          ret[i+j] += a[i] * b[j];
      for (int i=(int)ret.size()-1; i>=n; i--)
        for (int j=n-1; j>=0; j--)
          ret[i-j-1] += ret[i] * c[j];
      ret.resize(min((int) ret.size(), n));
      return ret;
    };

    vector<T> a = n == 1 ? vector<T>{c[0]} : vector<T>{0, 1}, x{1};
    for (; k>0; k/=2) {
      if (k % 2)
        x = mul(x, a);
      a = mul(a, a);
    }
    x.resize(n);

    T ret = 0;
    for (int i=0; i<n; i++)
      ret += x[i] * s[i];
    return ret;
}


const int N = 1e5;
const int K = 26;
int trie[N + 2][K];
int tc;
int cnt[N + 2];

void insert(const string &s) {
  int n = s.size();
  int root = 0;
  for (int i = 0; i < n; ++i) {
    int c = s[i] - 'a';
    if (!trie[root][c]) {
      trie[root][c] = ++tc;
    }
    root = trie[root][c];
  }
  cnt[root] = 1;
}

int suf[N];

void build() {
  queue<int> q;
  q.push(0);
  while (!q.empty()) {
    int u = q.front();
    cnt[u] += cnt[suf[u]];
    q.pop();
    for (int i = 0; i < K; ++i) {
      if (trie[u][i]) {
        suf[trie[u][i]] = (u > 0) * trie[suf[u]][i];
        q.push(trie[u][i]);
      } else {
        trie[u][i] = trie[suf[u]][i];
      }
    }
  }
}


void solve() {
  ll n, m;
  cin >> n >> m;
  vector<string> a(m);
  for (auto &x : a) {
    cin >> x;
    insert(x);
  }
  vector<M> pw(2021);
  pw[0] = 1;
  for (int i = 1; i < 2021; ++i) pw[i] = pw[i - 1] * 2;
  build();
  vector<M> dp(tc + 1);
  vector<M> s {0};
  M ans = 0;
  dp[0] = 1;
  for (int i = 1; i <= 4 * tc + 500; ++i) {
    vector<M> ndp(tc + 1);
    M cur = 0;
    for (int j = 0; j <= tc; ++j) {
      for (int k = 0; k < K; ++k) {
        int to = trie[j][k];
        ndp[to] += dp[j] * pw[cnt[to]];
        cur += dp[j] * pw[cnt[to]];
      }
    }
    dp = ndp;
    s.push_back(cur);
  }
  if (n < (int)s.size()) {
    cout << s[n] << '\n';
    return;
  }
  cout << solve(berlekampMassey(s), s, n) << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  // cin >> t;
  while(t--) {
    solve();
  }
}