Wanted help to reduce complexity from O^4 to O^3 or something like that. You're creating a new programming language with some exciting new features! Any programming language can check if two strings are matching, but you'd like yours to be able to check if they're "almost matching." More specifically, we'll say two strings are almost matching if they're equal in length and all of their corresponding characters are the same except for one. For example, "cat" and "bat" are almost matching, but "cat" and "dog" are not.

For the sake of efficiency, you're planning on testing the feature by using a single string and comparing its substrings. Given a string s and an integer k, your task is to find the number of pairs of substrings of s that are almost matching but differ at their k th character (0-based). It's necessary that the length of both substrings exceeds k (otherwise the strings wouldn't have a k th character).

Also note that substrings are determined by their indices, so there could potentially be multiple instances of the same word. For example, in the word "ingratiating" the substring "ing" beginning at index 0 is considered distinct from the one at index 9 (and there are also two distinct "ati" substrings).

Input/Output [Input] string s: A string consisting only of lowercase English letters.

[Input] integer k: 0≤k<s.length().

[Output] integer: The amount of different pairs as described above.

Constraints s.length(): 1≤s.length()<200.

k: 0≤k<s.length().

Execution time limit: 0.5 seconds (cpp).

Memory limit: 1 GB.

Example For s="abacaba" and k=1, the output should be 8. The 8 pairs are:

("aba", "aca") — i=0,j=2 and l=1,m=3.

("aba", "aca") — i=4,j=6 and l=1,m=3.

("aca", "aba") — i=2,j=4 and l=1,m=3.

("aca", "aba") — i=2,j=4 and l=1,m=3.

("ac", "ab") — i=2,j=3 and l=1,m=2.

("ac", "ab") — i=2,j=3 and l=3,m=4.

("ab", "ac") — i=0,j=1 and l=1,m=2.

("ab", "ac") — i=4,j=5 and l=1,m=2.