Count Beautiful Substrings II

Count the non-empty substrings where vowels == consonants and their product is divisible by k; since equality implies length 2t with t vowels, the problem reduces to counting substrings of length 2t that contain exactly t vowels for every t with t^2 % k == 0. Efficient solutions combine enumerating valid t (up to n/2) with prefix sums or sliding-window counting to handle strings up to 5·10^4.