Count Distinct Substrings

You are given a string ( s ) and an integer ( k ). Your task is to compute the number of distinct substrings of length exactly ( k ) in the string ( s ). A substring is defined as a contiguous sequence of characters within ( s ).

If ( k ) is greater than the length of ( s ), then no such substrings exist, and the output should be 0.

The input is provided via standard input (stdin) and the output must be printed to standard output (stdout).

For example, consider the case where ( s = ) "abcabc" and ( k = 3 ). The distinct substrings of length 3 are "abc", "bca", and "cab", so the output is 3.

inputFormat

The input consists of two lines:

• The first line contains the string ( s ), which is a non-empty sequence of lowercase letters.
• The second line contains the integer ( k ).

It is guaranteed that ( 1 \leq k \leq 10^5 ) and ( |s| \leq 10^5 ). Note that ( k ) may be larger than the length of ( s ).

outputFormat

Output a single integer representing the number of distinct substrings of ( s ) of length ( k ).## sample

abcabc
3

3