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 k in s and output the result modulo \(10^9+7\).

More formally, let \(S\) be the set of all substrings of s of length k. You need to find \(|S|\) (the number of distinct elements in \(S\)) and then output \(|S| \bmod 10^9+7\).

Input/Output: Your program must read from stdin and write to stdout.

inputFormat

The input consists of two lines:

1. The first line contains a non-empty string s.
2. The second line contains an integer k, where 1 \(\leq k \leq |s|\).

outputFormat

Output a single integer denoting the number of distinct substrings of length k in s modulo \(10^9+7\>.

abcabc
2

3