\(1\) 文字ずつ文字を伸ばしていくことを考えると、末尾のたかだか \(L=6\) 文字を状態としてもつ DP を考えることができます。 この DP を行列累乗を使って高速化することでこの問題を解くことができます。

計算量は \(O(8^L\log N)\) 時間となり、十分高速です。

また、\(N\lt L\) の場合はすべての長さ \(N\) の文字列に対して愚直に判定し、\(N\geq L\) の場合は \(N=L,L+1,\ldots,L+2^{L+1}\) の場合の問題を解いたあと Berlekamp–Massey 法で漸化式を求め、Bostan–Mori 法で求めたい値を得ることで時間計算量は \(O(4^L+2^L\log N)\) になります。

#include <bits/extc++.h>
#include <atcoder/modint>

int main() {
    using namespace std;
    using modint = atcoder::static_modint<998244353>;

    constexpr unsigned long max_bit_length{6};
    constexpr unsigned long dp_size{2UL << max_bit_length};

    // 1 回の遷移を表す行列
    vector coef(dp_size, vector<modint>(dp_size));
    for(unsigned long i{1}; i < dp_size / 2; ++i)coef[i * 2 % dp_size][i] = coef[i * 2 % dp_size + 1][i] = 1;
    for(unsigned long i{dp_size / 2}; i < dp_size; ++i)coef[i * 2 % dp_size | dp_size / 2][i] = coef[i * 2 % dp_size + 1 | dp_size / 2][i] = 1;

    unsigned long N, M;
    cin >> N >> M;

    // 部分文字列として s_i を含むような遷移を削除
    for(unsigned long i{}; i < M; ++i){
        string s;
        cin >> s;
        unsigned long x{};
        for(const auto c : s)(x *= 2) += c - 'a';
        const auto k{size(s)};
        for(unsigned long j{1}, j_upto{dp_size >> k}; j < j_upto; ++j)coef[(j << k) + x] = vector<modint>(dp_size);
    }

    // 行列積
    const auto mat_mul{[](auto&& lhs, auto&& rhs){
        const auto n{size(lhs)};
        vector ret(n, vector<modint>(n));
        for(unsigned long i{}; i < n; ++i)
            for(unsigned long j{}; j < n; ++j)
                for(unsigned long k{}; k < n; ++k)
                    ret[i][k] += lhs[i][j] * rhs[j][k];
        return ret;
    }};
    
    // 答えを求める
    vector result(dp_size, vector<modint>(dp_size));
    for(unsigned long i{}; i < dp_size; ++i)result[i][i] = 1;
    while(N){
        if(N & 1)result = mat_mul(result, coef);
        coef = mat_mul(coef, coef);
        N /= 2;
    }
    cout << transform_reduce(begin(result), end(result), modint{}, plus<>{}, [](auto&& i){return i[1];}).val() << endl;

    return 0;
}