まず最初に思いつくのは、 \(dp[\) 文字列の末尾 \(k\) 文字 \(] = \{\) その末尾を持つ文字列の個数 \(\}\) のような DP です。
残念ながら、この DP は時間計算量 \(O(c^k N)\) ( \(c=26\) は文字の種類数) であり、 \(k \le 10\) という面でも \(N \le 10^9\) という面でもとても間に合いません。
しかし、文字列の末尾の情報を一定程度持ちながら DP する必要はありそうです。どうすればよいでしょうか？

\(S\) の要素の接頭辞の集合を \(T\) とします。
例えば、 \(S=\{\) abc, abde, bcd \(\}\) であるとき、 \(T=\{\) (空文字列), a, ab, abc, abd, abde, b, bc, bcd \(\}\) です。
これを用いて先程の DP を改善することを考えます。現状の文字列の接尾辞として、 \(T\) の要素のうち最も長いものを維持しておけば情報は足りています。
例えば、 xyzab という文字列に対しては 「 b が接尾辞である」という情報だけでは次に c を加えて abc が部分文字列となる情報が欠落しますが、 \(T\) 中で最も長い「 ab が接尾辞である」という情報を持っておけば \(S\) の要素を部分文字列として検出するには十分です。

なお、ここまでの議論は次のように言い換えることもできます。

• 文字列集合 \(S\) に対して Aho–Corasick法 でオートマトンを構成し、現在いる頂点の番号を DP の添え字に持つ。

これで、 DP の添え字の種類数は \(O(|T|)=O(\sum|S_i|)\) まで落ちました。しかしながら、時間計算量 \(O(N c \sum |S_i|)\) では依然間に合いません。

この DP を更に高速化することを考えます。
現在の接尾辞 \(T_i\) と次に来る文字 \(c\) から、次の接尾辞 \(T_j\) が定まります。
このことから、行列 \(M_{i,j} = \{\) 接尾辞 \(T_i\) から接尾辞 \(T_j\) に行く文字 \(c\) の種類数 \(\}\) という行列が構成できます。
行列累乗を活用すると、 \(k\) 文字追加の遷移が \(M^k\) による遷移として実現できます。

その結果、遷移の予計算に \(O(c (\sum |S_i|)^3)\) 、行列累乗に \(O(\log N (\sum |S_i|)^3)\) といった時間計算量でこの問題に正解できます。

余談: この問題は NDPC-C を誤読したことで生まれた問題です。 NDPC-C も「オートマトンDP」と説明されていますが、本問題はより直接的にオートマトン上で DP をすることになります。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

const ll mod=998244353;

vector<vector<ll>> mmul(vector<vector<ll>> &l,vector<vector<ll>> &r){
  ll n=l.size();
  vector<vector<ll>> res(n,vector<ll>(n,0));
  for(ll i=0;i<n;i++){
    for(ll j=0;j<n;j++){
      for(ll k=0;k<n;k++){
        res[i][k]+=l[i][j]*r[j][k];
        res[i][k]%=mod;
      }
    }
  }
  return res;
}

bool issuffix(string &a,string &b){
  ll al=a.size(),bl=b.size();
  if(al<bl){return false;}
  for(ll i=0;i<bl;i++){
    if(a[al-1-i]!=b[bl-1-i]){return false;}
  }
  return true;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n,k;
  cin >> n >> k;
  vector<string> s(k);
  map<string,ll> mp;
  mp[""]=0;
  for(auto &nx : s){
    cin >> nx;
    string pref;
    for(auto &ny : nx){
      pref.push_back(ny);
      mp[pref]=0;
    }
  }
  
  ll vn=0;
  vector<string> vs;
  for(auto &nx : mp){
    vs.push_back(nx.first);
    nx.second=vn; vn++;
  }

  vector<ll> ban(vn,0);
  vector<vector<ll>> mat(vn,vector<ll>(vn,0));
  for(ll i=0;i<vn;i++){
    for(ll j=0;j<k;j++){
      auto pos=vs[i].find(s[j]);
      if(pos!=string::npos){
        ban[i]=1; break;
      }
    }
  }
  for(ll i=0;i<vn;i++){
    if(ban[i]){continue;}
    for(char c='a';c<='z';c++){
      string ss=vs[i];
      ss.push_back(c);
      ll tg=0;
      for(ll j=0;j<vn;j++){
        if(issuffix(ss,vs[j])){
          if(vs[tg].size()<vs[j].size()){tg=j;}
        }
      }
      if(ban[tg]==0){
        mat[i][tg]++;
      }
    }
  }
  vector<ll> vec(vn,0);
  vec[0]=1;
  while(n>0){
    if(n&1ll){
      vector<ll> nvec(vn,0);
      for(ll i=0;i<vn;i++){
        for(ll j=0;j<vn;j++){
          nvec[j]+=vec[i]*mat[i][j];
          nvec[j]%=mod;
        }
      }
      vec=nvec;
    }
    mat=mmul(mat,mat);
    n>>=1;
  }
  ll res=0;
  for(auto &nx : vec){res+=nx; res%=mod;}
  cout << res << "\n";
  return 0;
}