Count Num Ways

Reverse each contiguous window of length k, one at a time, and count the window positions for which the whole reversed string is strictly smaller than the original. Identical text at different positions is counted separately; windows whose reversal changes nothing are not counted.

输入格式

The input is a JSON array [s,k]. Original bounds: 2≤length in code points≤1000000, 1≤k≤min(length,20). The original statement does not restrict the character set; this site specifies Unicode scalar characters and lexicographic order by code point, allows whitespace, NUL, non-BMP and Unicode separator characters, and keeps the original characters in the JSON encoding.

输出格式

Output a single integer, the answer.

样例 1

输入：

["amazon",3]

输出：

1

样例 2

输入：

["ababa",2]

输出：

2

样例 3

输入：

["😀
\u0000",3]

输出：

1

样例说明

The outputs of the three public examples are 1; 2; and 1, checked by independent enumeration or direct simulation.