Oops!! It seems some javascript files did not load. Please hard reload(SHIFT + reload) your page.

**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.

114 successful submissions.