Almost Matching

You are adding a new operator to a programming language. Any language can test whether two strings match; yours will also test whether they almost match.

Two strings almost match when they have the same length and their corresponding characters are equal at every position except exactly one. For example cat and bat almost match, but cat and dog do not, and neither do cat and cat.

To exercise the feature you take a single string s and compare its substrings with one another. Given s and an integer k, count the pairs of substrings of s that almost match and whose one differing character is at 0-based index k of each substring.

Precisely, a pair is a choice of two starting indices i < j and one common length L such that

L >= k + 1, and both s[i .. i+L-1] and s[j .. j+L-1] lie inside s (otherwise the substrings would have no k-th character);
s[i + p] == s[j + p] for every p with 0 <= p < L and p != k;
s[i + k] != s[j + k].

Count how many such triples (i, j, L) exist.

A substring is identified by where it starts and how long it is, so the same word occurring at two different places gives two different substring instances. The two substrings of a pair may overlap. A pair is counted once: (A, B) and (B, A) are the same pair.

Input Format

The first line contains the string s.

The second line contains the integer k.

Output Format

Print a single integer — the number of almost-matching substring pairs whose differing character sits at index k.

Constraints

1 <= |s| <= 2000
s consists of lowercase English letters only
0 <= k <= |s| - 1
The answer never exceeds |s| * (|s| - 1) / 2, so it fits comfortably in a 32-bit signed integer; a 64-bit accumulator is still the safe habit.

Examples

Example 1

Input:

ab
0

Output:

Explanation: The only candidate is s[0..0] = "a" against s[1..1] = "b". They have length 1 >= k + 1 = 1, and they differ exactly at index 0. That is one pair.

Example 2

Input:

aba
0

Output:

Explanation: "a" at index 0 versus "b" at index 1 differ at index 0, and "b" at index 1 versus "a" at index 2 differ at index 0. The pair "a" at index 0 versus "a" at index 2 does not count, because those two substrings are equal rather than almost matching. Longer lengths fail as well: "ab" versus "ba" differs at both positions.

Example 3

Input:

aab
0

Output:

Explanation: s[0..0] = "a" versus s[2..2] = "b", and s[1..1] = "a" versus s[2..2] = "b". Both differ at index 0. The two "a"s are equal, so they are not almost matching.

Example 4

Input:

ababab
0

Output:

Explanation: Every one of the three a positions 0, 2, 4 pairs with every one of the three b positions 1, 3, 5 at length 1, giving 9 pairs. No longer length works, because after the differing first character the two tails start with different letters.

Example 5

Input:

abxaby
2

Output:

Explanation: The substrings must agree on their first two characters and differ on the third. s[0..2] = "abx" and s[3..5] = "aby" do exactly that. No other pair of starting positions shares a length-2 prefix, and neither substring can be extended because both already reach the end of s.

Example 6

Input:

abab
1

Output:

Explanation: A counted pair needs matching first characters and differing second characters. The only two starting positions with the same first character are 0 and 2, both a, but s[1] and s[3] are both b, so nothing differs at index 1.

Example 7

Input:

aaaaab
4

Output:

Explanation: Only the starts 0 and 1 leave room for a 4-th character. They share the prefix aaaa, and s[4] = a differs from s[5] = b, so "aaaaa" and "aaaab" form one pair. No longer length exists, since s[5] is the last character.

Notes

Lengths shorter than k + 1 are never counted, because such substrings have no character at index k.
A pair whose substrings are completely equal is not almost matching: exactly one position must differ.
Overlap is allowed, so i and j may be closer together than L.
Every admissible length is a separate pair. If two starting positions work for three different lengths, they contribute 3.
If no pair exists the answer is 0; for example any string of one repeated letter yields 0 for every k.