Consider extending the string one character by one, then you can consider a DP (Dynamic Programming) that maintains at most \(L=6\) last characters. You can optimize the DP using fast matrix exponentiation to solve this problem.

The complexity is \(O(8^L\log N)\), which is fast enough.

Alternatively, you can solve it naively if \(N\lt L\), and if \(N\geq L\), solve the problem for \(N=L,L+1,\ldots,L+2^{L+1}\), find the recurrence relations using Berlekamp–Massey algorithm, and then find the sought value using Bostan–Mori algorithm to reduce the complexity to \(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};

    // Matrix representing one transition
    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;

    // Erase transitions containing s_i as substring
    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);
    }

    // matrix product
    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;
    }};
    
    // Find the answer
    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;
}