**Defining substring**

For a string P with characters P_{1}, P_{2} ,…, P_{q}, let us denote by P[i, j] the substring P_{i}, P_{i+1} ,…, P_{j}.

**Defining longest common prefix**

LCP(S_{1}, S_{2} ,…, S_{K}), is defined as largest possible integer j such that S_{1}[1, j] = S_{2}[1, j] = … = S_{K}[1, j].

You are given an array of N strings, A_{1}, A_{2} ,…, A_{N} and an integer K. Count how many indices (i, j) exist such that 1 ≤ i ≤ j ≤ N and LCP(A_{i}, A_{i+1} ,…, A_{j}) ≥ K. Print required answer modulo 10^{9}+7.

**Note that K does not exceed the length of any of the N strings. K <= min(len(A_i)) for all i**

For example,

```
A = ["ab", "ac", "bc"] and K=1.
LCP(A[1, 1]) = LCP(A[2, 2]) = LCP(A[3, 3]) = 2
LCP(A[1, 2]) = LCP("ab", "ac") = 1
LCP(A[1, 3]) = LCP("ab", "ac", "bc") = 0
LCP(A[2, 3]) = LCP("ac", "bc") = 0
So, answer is 4.
```

**Return your answer % MOD = 1000000007**

**Constraints**

1 ≤ Sum of length of all strings ≤ 5*10^{5}

Strings consist of small alphabets only.

NOTE:You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.

- Hints are not available for this problem

Loading...