One my come up with the following DP (Dynamic Programming) in the first place: \(dp[\)length-\(k\) suffix\(] = \{\)the number of strings having suffix\(\}\).
Unfortunately, this DP costs \(O(c^k N)\) time (where \(c=26\) is the size of the alphabet); neither \(k \le 10\) nor \(N \le 10^9\) gives any chance of completing it within the time limit.
But it seems we need to maintain some kind of information about the suffix. How can we do that?

Let \(T\) be the set of suffixes of the elements in \(S\).
For example, if \(S=\{\) abc, abde, bcd \(\}\), we have \(T=\{\) (empty string), a, ab, abc, abd, abde, b, bc, bcd \(\}\).
Consider optimizing the DP above based on this. It is sufficient to remember the longest suffix of the current string contained in \(T\).
For example, for a string xyzab, just remembering that “b is a suffix” loses the information that appending c makes abc a substring, but remembering that “ab is a suffix”, which is the longest among \(T\), is sufficient to detect an element of \(S\) as a substring.

The discussions so far can be rephrased as follows:

• For the set of strings \(S\), apply Aho-Corasick algorithm to construct an automaton, and maintain the current vertex number as a key of the DP.

Now the number of keys has been reduced to \(O(|T|)=O(\sum|S_i|)\). However, the time complexity \(O(N c \sum |S_i|)\) is still not fast enough.

Let us try to optimize the DP further.
The current suffix \(T_i\) and the succeeding character \(c\) determines the next suffix \(T_j\).
This property allows to construct a matrix \(M_{i,j} = \{\)the number of distinct characters \(c\) that transitions suffix \(T_i\) to suffix \(T_j\)\(\}\).
Using matrix exponentiation, transitions by appending \(k\) characters is realized as \(M^k\).

As a result, the problem can be solved in \(O(c (\sum |S_i|)^3)\) time for the precalculation of the transitions, and \(O(\log N (\sum |S_i|)^3)\) time for the matrix exponentiation.

Bonus: this problem originates from NDPC-C, but misread. While NDPC-C is explained as an “automaton DP,” this problem also performs DP on an automaton more explicitly.

Sample code (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;
}