Chainword
Contest: Educational Codeforces Round 107 (Rated for Div. 2)
Difficulty rating: 2700
Tags: brute force, data structures, dp, matrices, string suffix structures, strings

A chainword is a special type of crossword. As most of the crosswords do, it has cells that you put the letters in and some sort of hints to what these letters should be.

The letter cells in a chainword are put in a single row. We will consider chainwords of length $$$m$$$ in this task.

A hint to a chainword is a sequence of segments such that the segments don't intersect with each other and cover all $$$m$$$ letter cells. Each segment contains a description of the word in the corresponding cells.

The twist is that there are actually two hints: one sequence is the row above the letter cells and the other sequence is the row below the letter cells. When the sequences are different, they provide a way to resolve the ambiguity in the answers.

You are provided with a dictionary of $$$n$$$ words, each word consists of lowercase Latin letters. All words are pairwise distinct.

An instance of a chainword is the following triple:

- a string of $$$m$$$ lowercase Latin letters;
- the first hint: a sequence of segments such that the letters that correspond to each segment spell a word from the dictionary;
- the second hint: another sequence of segments such that the letters that correspond to each segment spell a word from the dictionary.

Note that the sequences of segments don't necessarily have to be distinct.

Two instances of chainwords are considered different if they have different strings, different first hints or different second hints.

Count the number of different instances of chainwords. Since the number might be pretty large, output it modulo $$$998\,244\,353$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 8$$$, $$$1 \le m \le 10^9$$$) — the number of words in the dictionary and the number of letter cells.

Each of the next $$$n$$$ lines contains a word — a non-empty string of no more than $$$5$$$ lowercase Latin letters. All words are pairwise distinct.

Output format:
Print a single integer — the number of different instances of chainwords of length $$$m$$$ for the given dictionary modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
Here are all the instances of the valid chainwords for the first example:

The red lines above the letters denote the segments of the first hint, the blue lines below the letters denote the segments of the second hint.

In the second example the possible strings are: "abab", "abcd", "cdab" and "cdcd". All the hints are segments that cover the first two letters and the last two letters.

Example input:
3 5
ababa
ab
a

Example output:
11

Example input:
2 4
ab
cd

Example output:
4

Editorial:
Let's use a trie to store the given words. Now let's imagine a procedure that checks if some string of length $$$m$$$ can be represented as a concatenation of some of these words. If the words were prefix-independent — no word was a prefix of another word, that task would be solvable with a greedy algorithm.
We could iterate over a string and maintain the current vertex of the trie we are in. Append a current letter. If there is no such transition in a trie, it can't be represented. If the vertex we go to is a terminal, jump to the root of the trie. Otherwise, just go to that vertex.
However, since the words aren't prefix-independent, we have a terminal on a path to other terminals. Thus, we can't immediately decide if we should jump to the root or just go.
Let's handle this with dynamic programming. $$$dp[i][v]$$$ — can we put $$$i$$$ letters in such a way that the vertex of a trie we are in is $$$v$$$.
Is building a chainword letter by letter that different from this process? Apparently, it isn't. Consider $$$dp[i][v][u]$$$ — how many ways are there to put $$$i$$$ letters in a string so that the first hint is in a vertex $$$v$$$ and the second hint is in a vertex $$$u$$$. For the transition we can try all $$$26$$$ letters to put and jump to the corresponding vertices.
That obviously, is too slow. The intuition tells us that this dp should be calculated with some kind of matrix exponentiation (since $$$m \le 10^9$$$). That dp can be rewritten as a matrix pretty easily. However, its size is up to $$$1681 \times 1681$$$ (the maximum number of vertices in a trie squared).
Some say that there is a way to compute the $$$m$$$-th power of such a huge matrix fast enough with Berlekamp–Massey, but I unfortunately am not familiar with it.
Thus, we'll have to reduce the size of our matrix. First, notice that the only reachable states $$$(v, u)$$$ are such that the word that is written on a path from the root to $$$v$$$ is a suffix of a word that is written on a path from the root to $$$u$$$ or vice versa.
Look at it the other way: if we build a trie on the reversed words, then one of the vertices will be an ancestor of another one. Now it's easy to estimate the number of states as the sum of depths of all vertices. However, since we look at ordered pairs of $$$(v, u)$$$, we should more or less double that amount. That should be $$$241$$$ states at max.
This can probably pass with an optimal enough implementation. We can do better, though. Let's merge the states $$$(v, u)$$$ and $$$(u, v)$$$ into one state. The intuition is basically that you can swap the hints at will. That makes the pairs unordered: now there are up to $$$161$$$ pairs. That surely will work fast enough.
The way to generate all the possible states is the following: run a dfs/bfs, starting from $$$(0, 0)$$$ that makes all valid transition and record all the states that can be visited.
While preparing the tests, I only managed to get up to $$$102$$$ states and I would really love to hear an approach to either prove a tighter bound or to generate a test closer to the bound of $$$161$$$.