First, fix a string . Scan it from left to right, and choose a substring as soon as one of the given strings ends. Then repeat the process using only the characters to the right of the chosen substring. This greedy strategy of choosing the earliest-ending occurrence computes .
Represent this process with an Aho--Corasick automaton. Insert the given strings into a trie, then build the failure links and transitions for every letter. Mark a state if a given string ends there, including strings found through failure links. This is a Boolean mark: duplicate given strings do not increase it.
If reading a letter from state reaches a marked state, choose one substring and return to the root. Otherwise, remain in the reached state. These rules determine the next state and whether the number of chosen substrings increases by one for each letter transition. Returning to the root discards the information read through the end of the chosen substring, preventing the next choice from overlapping it.
Since the process never remains in a marked state, exclude such states from the matrix. Let be the number of remaining states, and number them from through , with state being the root.
Now process all strings of a given length together. Let be the number of strings reaching state , and let be the sum of the numbers of chosen substrings over all these strings. Let be the number of letters that take state to state under the rules above, and let be the number of letters that cause a substring to be chosen. Appending one letter gives
Every existing string has extensions, so its previous number of chosen substrings contributes to each extension, giving the term .
These equations define a transition matrix for the row vector . Put in the upper-left block and in the first entries of the last column. The last row is zero except for its last entry, which is .
The empty string reaches the root and has no chosen substrings, so the initial vector is . Compute the -th power of the transition matrix by binary exponentiation, multiply the initial vector by it, and output the last coordinate. Perform all calculations modulo .
Let . The automaton has at most states, and at least one state is marked, so . The time complexity is , and the space complexity is .
Proof
Among the valid substrings in the remaining portion of the string, let be an occurrence ending as early as possible. Let be the first occurrence in an optimal selection. The end of is no later than the end of . Replacing with therefore does not overlap any subsequent chosen occurrence. Thus, there is an optimal selection starting with . Repeating this argument on the portion to its right proves the greedy strategy optimal. If no valid occurrence exists, neither strategy chooses anything.
Solution written by GPT6
The automaton state represents the longest suffix of the characters read since the last choice that is also a trie prefix. Propagating marks through failure links detects every given string ending at the current position. Choosing one occurrence at the first marked state and returning to the root follows exactly the greedy strategy above. If several strings end at the same position, only one is chosen. The remaining portion is the same whichever of those occurrences is chosen.
Assume that and correctly describe all strings of some length. Each pair consisting of an existing string and a letter produces exactly one next string, so summing the counts over transitions gives . Every extension inherits the previous number of choices, contributing in total. For each string at state , exactly letters add one new choice, contributing in total. Hence, both transition equations preserve their definitions at the next length.
The initial vector correctly describes the empty string. After transitions, its last coordinate is the sum of the greedy counts over all strings of length . Since the greedy count equals for every string, this coordinate is the required answer.
