<p>Given the strings <code>s1</code> and <code>s2</code> of size <code>n</code> and the string <code>evil</code>, return <em>the number of <strong>good</strong> strings</em>.</p>

<p>A <strong>good</strong> string has size <code>n</code>, it is alphabetically greater than or equal to <code>s1</code>, it is alphabetically smaller than or equal to <code>s2</code>, and it does not contain the string <code>evil</code> as a substring. Since the answer can be a huge number, return this <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2, s1 = &quot;aa&quot;, s2 = &quot;da&quot;, evil = &quot;b&quot;
<strong>Output:</strong> 51 
<strong>Explanation:</strong> There are 25 good strings starting with &#39;a&#39;: &quot;aa&quot;,&quot;ac&quot;,&quot;ad&quot;,...,&quot;az&quot;. Then there are 25 good strings starting with &#39;c&#39;: &quot;ca&quot;,&quot;cc&quot;,&quot;cd&quot;,...,&quot;cz&quot; and finally there is one good string starting with &#39;d&#39;: &quot;da&quot;.&nbsp;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 8, s1 = &quot;leetcode&quot;, s2 = &quot;leetgoes&quot;, evil = &quot;leet&quot;
<strong>Output:</strong> 0 
<strong>Explanation:</strong> All strings greater than or equal to s1 and smaller than or equal to s2 start with the prefix &quot;leet&quot;, therefore, there is not any good string.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 2, s1 = &quot;gx&quot;, s2 = &quot;gz&quot;, evil = &quot;x&quot;
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>s1.length == n</code></li>
	<li><code>s2.length == n</code></li>
	<li><code>s1 &lt;= s2</code></li>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>1 &lt;= evil.length &lt;= 50</code></li>
	<li>All strings consist of lowercase English letters.</li>
</ul>

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        return self._sol2(n, s1, s2, evil)

    # Alright, down to passing 41 out of 55, once I worked out some tiny bugs on the original 3 sample tests.
    # Alright as i investigate this test case, it's the one with evil string kpvphwnkrtxuiuhb and 93-long sources.
    #   I can see that it never exists directly in them. The sources don't even have the first two characters 'kp' as subseries!
    #   And there are no overlaps of evil string with itself.
    #   So far I'm trying to get it to fail on shorter versions of these, so far up to 31 characters in my smaller test case, that
    #   smaller one is still passing. 38 passed. 39. 46. Okay at 49 we finally failed. I strongly suspect it's because we rolled over
    #   our mod. (which we did between those) Alright, and 48 passed. Does seem to happen exactly where the answer rolls over.
    #   Ugh rolling over wasn't quite the issue. So in the 48 char case, when just copying shorter suffixes from the 93 char case, our
    #   leading characters were y and z. So I tried changing the first to 'u' so that we'd have more good strings and get rollover even
    #   with 48 characters total. And I did seem to get rollover! when from like 9 hundred million something to 24 million something.
    #   But the answer was still right. I also changed first one to 'a' just now for even more, and it still works!
    #   And how can we be just 13 off?? Oh weird. ord(d) + 13 = ord(q). Jesus I changed the first char of s1 from d to o, diff of 2
    #   now, and that's how much we're off by. Red-hot lead.
    #   Alright I took out all the mods except for the very last necessary one. And again, all test cases pass except for this one,
    #   which is off by 2. And the rest of the numbers are totally different, of course! All the digits are totally different when I
    #   change to 'n' from 'o' (well maybe not all, you get the idea). But now off by 3, as expected.
    #   Alright, wasn't finding anything profitable, I tried messing around with other test cases, like the same length of strings but
    #   shorter evil string. And I got around to finding that when the sources are 46 long and the string is 15 long, we again are off
    #   by the diff in the first character ord(). And that failing case? It was 16 long and 49 long source. 3x + 1.
    #   Hmm, and specifically when we are off in these cases, we are too high by those amounts. Meaning we are overcounting the
    #   sources (quite unlikely, since this depends on the evil length) or we are undercounting the evil strings.
    #   Okay! Getting much easier test cases. strings of length 7, e_len of 2, again we're off by that diff in first char.
    #   AND when sources are len 4 and e_len of 1. Hey, now this one is very valuable because the numbers are less than 20k.
    #   There's no mod rollover, so we can totally remove that as culprit, plus it makes it far easier to think things through.
    #   But yeah that no rollover is helpful. Okay, s1 = aaaa, s2 = baaa, e = c. Good simple test case, we're 1 too high.
    # Alright found the bug, not yet sure on best way to address but recording the problem. Consider the number of times you can fit
    #   'a' into 'aaa'. Our rough total is to place in each position and count all other possibilities from that (676 for each). How
    #   many times is 'aa(not-a)' produced? 2 * 25 = 50, in total. But think specifically, say 'aaf'. It is produced *twice*, when we
    #   calculate off all possibilities with a in the first position, and the second. Now consider 'aaa'. It is produced *three* times
    #   because once for each position of a. That means there are *2* duplicates of it. So while I was basically correct with the
    #   logic that exactly 2 evil strings in a block, plus dupes, can be subtracted from our naive rough total, I didn't factor *how
    #   many* times each duplicate should be removed.
    def _sol2(self, n: int, s1: str, s2: str, evil: str) -> int:
        MOD = 1_000_000_007
        ord_a = ord("a")
        xe = [ord(c) - ord_a for c in evil]
        sources = [[ord(c) - ord_a for c in s1], [ord(c) - ord_a for c in s2]]
        e_len = len(xe)
        overlaps = []
        for i in range(1, e_len):
            if xe[i:] == xe[:e_len - i]:
                overlaps.append(i)
        #print(overlaps)
        
        @cache
        def _pow(i : int) -> int:
            return (26 ** i) % MOD

        @cache
        def _block_uniques(block_len: int) -> int:
            if block_len < e_len:
                return 0
            # Multiply the number of evil strings in a block one smaller by 26, the number of possibilities for the character spot we
            # just added.
            # Then add the number of evil strings that have an evil string *only* starting from this position.
            return (26 * _block_uniques(block_len - 1) + _first_place_only(block_len)) % MOD
        
        # This function calculates the number of unique strings of length str_len that have evil string at the beggining AND NO WHERE
        # ELSE.
        @cache
        def _first_place_only(str_len: int) -> int:
            # First calculate the total number of strings of this length that begin with the evil string
            free_chars = str_len - e_len
            if free_chars < 0:
                return 0
            total = _pow(free_chars)
            # Remove the number of strings which contain evil string in that trailing block 
            total -= _block_uniques(free_chars)
            # Remove the number of strings which contain evil string in an overlap position with the one at the beginning of str_len
            for overlap_i in overlaps:
                total -= _first_place_only(str_len - overlap_i)
            return total % MOD
        
        # This is used when the first character of evil is the "top" character of a digit.
        # Return 0 if the rest of the comparison string will not contain the evil string starting at this position
        # Return 1 if it contains it and also has "higher" strings not covered by the evil string (src: "ab", evil: "aa")
        # Return 2 if ALL further values of comparison string will contain evil string (src: "aab", evil: "aa")
        @cache
        def _compare_evil(source_id: int, source_index: int) -> int:
            #print(f"compare evil {source_id} {source_index}")
            for i in range(e_len):
                #print(sources[source_id][source_index + i], xe[i])
                if sources[source_id][source_index + i] > xe[i]:
                    return 1
                if sources[source_id][source_index + i] < xe[i]:
                    return 0
            return 2

        # Calculate the total strings <= both s1 and s2
        # We'll maintain data on the "top remainder counts" at each index, which can be valuable in certain cases when getting
        # evil counts.
        counts_source = [[0] * n, [0] * n]
        for s_i in range(2):
            # Note that we don't add 1 to "larger" earlier characters, because for those characters we are calculating only the
            # complete blocks *below* that character, while the number of strings that start with the top character is determined
            # by "smaller" later characters. The only exception is the smallest/last character
            counts_source[s_i][n - 1] = sources[s_i][n - 1] + 1
            for i in range(n - 2, -1, -1):
                # n - i - 1 starts at 1 and goes up 1 every iteration
                counts_source[s_i][i] = (sources[s_i][i] * _pow(n - i - 1) + counts_source[s_i][i + 1]) % MOD
        # At this point counts_source[x][0] is the total number of strings equal or lesser than s1 and s2 respectively
        is_top_of_s1_included = xe != sources[0][n - e_len:] # Used at the end to determine if we add 1, as s1 is an inclusive bound
        #print("is_top_of_s1", is_top_of_s1_included)
        # Now calculate the total number of evil characters equal to or less than s1 and s2 respectively
        evil_counts = [0, 0]
        for s_i in range(2):
            # The value of x[i] is how many complete blocks lie below this one, e.g. 0 for 'a', 2 for 'c'
            # We begin by calculating the number of unique strings with the evil substring in the block one smaller than this, and
            # multiplying by the number of characters in this location. This calculation only applies to characters smaller than this
            # character. For example for character 'd' (value 3) there are 3 characters less than it, a, b, and c.
            for i in range(n - e_len + 1):
                #print(f"checking evil for s_i {s_i} at {i}")
                evil_counts[s_i] += (sources[s_i][i] * _block_uniques(n - i - 1)) % MOD
                #print(evil_counts[s_i])
                # Add the substrings that have the evil string ONLY beginning at index i, which were not calculated above
                evil_match = _compare_evil(s_i, i)
                #print(evil_match)
                if evil_match == 1:
                    # Add the count of these strings and move on
                    evil_counts[s_i] += _first_place_only(n - i)
                    #print(evil_counts[s_i])
                elif evil_match == 2:
                    #print("evil match 2") # As expected, we are not hitting this in our problem case
                    # We actually cover all remaining counts of this source as evil characters
                    evil_counts[s_i] += counts_source[s_i][i + 1] if i < n - e_len else 1
                    #print(evil_counts[s_i])
                    if s_i == 0:
                        is_top_of_s1_included = False
                    break
        #print(counts_source)
        #print(evil_counts)
        good_1 = counts_source[0][0] - evil_counts[0]
        good_2 = counts_source[1][0] - evil_counts[1]
        return (good_2 - good_1 + is_top_of_s1_included) % MOD




    def _old_sol1_code() -> None:
        # Calculate the total number that have at least one instance of evil string, INCLUDING duplicate counts from having more
        # than one instance.
        free_chars = block_len - e_len
        number_of_locations = free_chars + 1
        one_or_more_with_dupes = number_of_locations * _pow(free_chars)
        # Now calculate the number that have at least two instances, again WITH duplicates (that have three or more).
        two_or_more_with_dupes = 0
        # First calculate the value when there is no overlap of the two evil strings.
        free_chars = block_len - 2 * e_len
        if free_chars >= 0:
            # Determine the number of combinations of fitting two non-overlapping evil strings in. This is equivalent to choosing,
            # with replacement, sets of size free_chars, each character of which can go before both, between them, or after both.
            # The formula for multiset combinations is n + k - 1 choose k. k = free_chars, n = 3.
            two_or_more_with_dupes = math.comb(2 + free_chars, free_chars) * _pow(free_chars)
        if block_len == 3:
            print(free_chars, one_or_more_with_dupes, two_or_more_with_dupes)
        # Now add ways we can have two or more duplicates WITH overlap
        for overlap_i in overlaps:
            free_chars = block_len - (e_len + overlap_i)
            if free_chars >= 0:
                number_of_locations = free_chars + 1
                two_or_more_with_dupes += number_of_locations * _pow(free_chars)
        # Our desired value is one or more WITHOUT duplicates. At this point we have a value that is one or more WITH duplicates,
        # meaning, we've double-counted strings that have 2 or more instances of evil string. We also have a value that is two or
        # more WITH duplicates, meaning it double-counts strings that have 3 or more instances of evil string.
        # In other words, the second value is the number of duplicates that were double-counted in the first value. So we simply
        # subtract.
        return one_or_more_with_dupes - two_or_more_with_dupes

    # This approach passed 13 test cases, out of a lot more than that, there's something to it in many cases but 1) I have a much
    # better idea, and 2) I'm not sure my recursive relations hold/are-correct.
    def _sol1(self, n: int, s1: str, s2: str, evil: str) -> int:
        MOD = 1_000_000_007
        x1 = [ord(c) - 97 for c in s1]
        x2 = [ord(c) - 97 for c in s2]
        xe = [ord(c) - 97 for c in evil]
        def match_evil(i: int) -> int:
            if n - i < len(evil):
                return 0
            upper_match, lower_match = True, True
            j = 0
            while i + j < n and j < len(evil) and (upper_match or lower_match):
                if upper_match:
                    if evil[j] > s2[i + j]:
                        return 0
                    elif evil[j] < s2[i + j]:
                        upper_match = False
                if lower_match:
                    if evil[j] < s1[i + j]:
                        return 0
                    elif evil[j] > s1[i + j]:
                        lower_match = False
                j += 1
            if upper_match:
                return 3
            if lower_match:
                return 1
            return 2
        multipliers = [0] * n
        counts_1 = [0] * n
        counts_2 = [0] * n
        for i in range(n - 1, -1, -1):
            if i == n - 1:
                multipliers[i] = 1
                counts_1[i] = x1[i] + 1
                counts_2[i] = x2[i] + 1
            else:
                multipliers[i] = (26 * multipliers[i + 1]) % MOD
                counts_1[i] = (x1[i] * multipliers[i] + counts_1[i + 1]) % MOD
                counts_2[i] = (x2[i] * multipliers[i] + counts_2[i + 1]) % MOD
        # pad these by one to simplify algorithm, but this is still 0-indexed
        past_evils = [0] * (n + 1)
        past_ks = [0] * n
        for i in range(n - len(evil), -1, -1):
            print(i)
            evils = [0] * (n + 1)
            ks = [0] * n
            evil_match = match_evil(i)
            last_match = i # Used in our calculation of how many to add for long "empty" chains. Default to i.
            for j in range(i, -1, -1):
                # Start by calculating the new evil strings we add by expanding j leftward by 1 (or starting our loop)
                if j == i:
                    if evil_match:
                        pre_evil = i + len(evil)
                        if pre_evil == n:
                            evils[j] = 1
                        else:
                            if evil_match == 3: # Exact match to s2, for this substring length
                                evils[i] = counts_2[pre_evil]
                            elif evil_match == 2: # In between s1 and 2, in this substring length
                                evils[i] = multipliers[pre_evil - 1]
                            elif evil_match == 1: # Exact match to s1, for this substring length
                                evils[i] = multipliers[pre_evil - 1] - counts_1[pre_evil]
                        last_match = j
                else:
                    diff = max(0, x2[j] - x1[j])
                    if diff:
                        k = 1
                        k_mult = 1
                        while j + k != last_match:
                            k += 1
                            k_mult *= 26
                        multiplied_value = evils[last_match]
                        if k > 1 or not multiplied_value:
                            ks[j] = k_mult
                        if not multiplied_value:
                            multiplied_value = 1
                        evils[j] = (diff * k_mult * multiplied_value)
                        last_match = j
                # Add however many we had when j was one larger
                evils[j] += evils[j + 1]
                # Add however many we had when i was one larger
                evils[j] += past_evils[j]
                if past_evils[j]:
                    if evils[j + 1]:
                        # Subtract the amount we had when both were 1 larger, to avoid double-counting
                        evils[j] -= past_evils[j + 1]
                    # If we had a match here, subtract the shadow values
                    if evil_match:
                        evils[j] -= past_ks[j]
                evils[j] = evils[j]
            print(evils)
            print(ks)
            past_evils = evils
            past_ks = ks
        print(multipliers)
        print(counts_1)
        print(counts_2)
        print((counts_2[0] - counts_1[0]) % MOD)
        return max(0, (counts_2[0] - counts_1[0] - evils[0] + 1)) % MOD
        
17800