<p>You are given a string <code>s</code> and a positive integer <code>k</code>.</p>

<p>Let <code>vowels</code> and <code>consonants</code> be the number of vowels and consonants in a string.</p>

<p>A string is <strong>beautiful</strong> if:</p>

<ul>
	<li><code>vowels == consonants</code>.</li>
	<li><code>(vowels * consonants) % k == 0</code>, in other terms the multiplication of <code>vowels</code> and <code>consonants</code> is divisible by <code>k</code>.</li>
</ul>

<p>Return <em>the number of <strong>non-empty beautiful substrings</strong> in the given string</em> <code>s</code>.</p>

<p>A <strong>substring</strong> is a contiguous sequence of characters in a string.</p>

<p><strong>Vowel letters</strong> in English are <code>&#39;a&#39;</code>, <code>&#39;e&#39;</code>, <code>&#39;i&#39;</code>, <code>&#39;o&#39;</code>, and <code>&#39;u&#39;</code>.</p>

<p><strong>Consonant letters</strong> in English are every letter except vowels.</p>

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

<pre>
<strong>Input:</strong> s = &quot;baeyh&quot;, k = 2
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are 2 beautiful substrings in the given string.
- Substring &quot;b<u>aeyh</u>&quot;, vowels = 2 ([&quot;a&quot;,e&quot;]), consonants = 2 ([&quot;y&quot;,&quot;h&quot;]).
You can see that string &quot;aeyh&quot; is beautiful as vowels == consonants and vowels * consonants % k == 0.
- Substring &quot;<u>baey</u>h&quot;, vowels = 2 ([&quot;a&quot;,e&quot;]), consonants = 2 ([&quot;b&quot;,&quot;y&quot;]).
You can see that string &quot;baey&quot; is beautiful as vowels == consonants and vowels * consonants % k == 0.
It can be shown that there are only 2 beautiful substrings in the given string.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;abba&quot;, k = 1
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are 3 beautiful substrings in the given string.
- Substring &quot;<u>ab</u>ba&quot;, vowels = 1 ([&quot;a&quot;]), consonants = 1 ([&quot;b&quot;]).
- Substring &quot;ab<u>ba</u>&quot;, vowels = 1 ([&quot;a&quot;]), consonants = 1 ([&quot;b&quot;]).
- Substring &quot;<u>abba</u>&quot;, vowels = 2 ([&quot;a&quot;,&quot;a&quot;]), consonants = 2 ([&quot;b&quot;,&quot;b&quot;]).
It can be shown that there are only 3 beautiful substrings in the given string.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;bcdf&quot;, k = 1
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are no beautiful substrings in the given string.
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= k &lt;= 1000</code></li>
	<li><code>s</code> consists of only English lowercase letters.</li>
</ul>

class PrimeSPFsieve:
    """
    Finds the smallest prime factor for each number and the number of times
    it divides the number and generates a list of primes.
    Methods primeFactors() and primeFactorisation() use this sieve to
    identify unique prime factors and find the factorisation of a given
    positive integer respectively
    """
    def __init__(self, n_max: Optional[int]=None):
        if n_max is None: n_max = 2
        self.sieve = [(-1, 0, 1)] * 2
        self.sieve.append((2, 1, 1))
        self.sieve.append((3, 1, 1))
        #self.use_p_lst = use_p_lst
        #if use_p_lst:
        self.p_lst = [2, 3]
        self.extendSieve(n_max)
    
    def extendSieve(self, n_max: int) -> None:
        """
        Extends the sieve to n_max
        """
        n_orig = len(self.sieve) - 1
        if n_orig >= n_max: return
        sieve = self.sieve
        p_lst = self.p_lst
        sieve.extend([(x, 1, 1) for x in range(n_orig + 1, n_max + 1)])
        for p in p_lst:
            if p * p > n_max: break
            for i in range(max(p, (n_orig // p) + 1), (n_max // p) + 1):
                i2 = p * i
                if p > sieve[i2][0]: continue
                sieve[i2] = (p, sieve[i][1] + 1, sieve[i][2]) if sieve[i][0] == p else (p, 1, i)
        
        def incorporatePrime(p: int) -> None:
            if sieve[p][0] == p: p_lst.append(p)
            else: return
            for i in range(max(p, (n_orig // p) + 1), (n_max // p) + 1):
                i2 = p * i
                if p > sieve[i2][0]: continue
                sieve[i2] = (p, sieve[i][1] + 1, sieve[i][2]) if sieve[i][0] == p else (p, 1, i)
            return
        # Using the fact that primes greater than 2 are 1 modulo 2
        start = n_orig + 1 + (n_orig & 1)
        end = math.isqrt(n_max)
        p = start - 2
        for p in range(start, end + 1, 2):
            incorporatePrime(p)
        for p in range(p + 2, n_max + 1, 2):
            if sieve[p][0] == p: p_lst.append(p)
        return

    def primeFactorisation(self, n: int) -> Dict[int, int]:
        """
        Gives the prime factorisation of a strictly positive integer.
        Note that by the Fundamental Theorem of Arithmetic this
        factorisation is guaranteed to be unique.
        
        Args:
            Required positional:
            n (int): The strictly positive integer of which the prime
                    factorisatio is to be found.
        
        Returns:
        Dictionary (dict) whose keys are the complete set of prime
        factors of n (as ints) and whose values are the corresponding
        power of that prime in the factorisation (also as ints).
        """
        self.extendSieve(n)
        sieve = self.sieve
        res = {}
        while n != 1:
            res[sieve[n][0]] = sieve[n][1]
            n = sieve[n][2]
        return res

class Solution:
    ps = PrimeSPFsieve()
    def beautifulSubstrings(self, s: str, k: int) -> int:
        vowels = set("aeiou")
        k_pf = self.ps.primeFactorisation(k)
        k2 = 2
        for p, f in k_pf.items():
            k2 *= p ** ((f + 1) >> 1)
        
        prev = {0: {0: 1}}
        res = 0
        bal = 0
        for i, l in enumerate(s, start=1):
            bal += 1 if l in vowels else -1
            i2 = (i % k2)
            prev.setdefault(i2, {})
            prev[i2].setdefault(bal, 0)
            res += prev[i2][bal]
            prev[i2][bal] += 1
        return res
226