<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>

def _compute_lps(s: str) -> list[int]:
    n = len(s)
    lps = [0] * n
    i = 1
    match_len = 0

    while i < n:
        if s[i] == s[match_len]:
            match_len += 1
            lps[i] = match_len
            i += 1
        else:
            if match_len > 0:
                match_len = lps[match_len - 1]
            else:
                i += 1

    return lps


class Solution:
    def __init__(self) -> None:
        self.n: int = 0
        self.s1: str = None
        self.s2: str = None
        self.evil: str = None
        self.dp: list[list[list[list[int]]]] = []
        self.lps: list[int] = []

    def __find_good_strings_handler(
        self,
        idx: int,
        evil_length: int,
        left_bound_passed: bool,
        right_bound_passed: bool,
    ):
        if evil_length >= len(self.evil):
            return 0

        if idx >= self.n:
            return 1

        if self.dp[idx][evil_length][left_bound_passed][right_bound_passed] != -1:
            return self.dp[idx][evil_length][left_bound_passed][right_bound_passed]

        MOD = 10**9 + 7
        result = 0
        left_bound = ord(self.s1[idx]) if left_bound_passed else ord("a")
        right_bound = ord(self.s2[idx]) if right_bound_passed else ord("z")

        for ch in range(left_bound, right_bound + 1):
            j = evil_length
            while j > 0 and ord(self.evil[j]) != ch:
                j = self.lps[j - 1]
            if ord(self.evil[j]) == ch:
                j += 1
            result = (
                result
                + self.__find_good_strings_handler(
                    idx=idx + 1,
                    evil_length=j,
                    left_bound_passed=left_bound_passed and (ch == left_bound),
                    right_bound_passed=right_bound_passed and (ch == right_bound),
                )
            ) % MOD

        self.dp[idx][evil_length][left_bound_passed][right_bound_passed] = result

        return result

    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        self.n = n
        self.s1 = s1
        self.s2 = s2
        self.evil = evil
        self.lps = _compute_lps(evil)
        self.dp = [
            [[[-1 for _ in range(2)] for __ in range(2)] for ___ in range(len(evil))]
            for ____ in range(n)
        ]

        return self.__find_good_strings_handler(
            idx=0, evil_length=0, left_bound_passed=True, right_bound_passed=True
        )

21200