Longest Common Prefix II

Defining substring
For a string P with characters P₁, P₂ ,…, P_q, let us denote by P[i, j] the substring P_i, P_i+1 ,…, P_j.

Defining longest common prefix
LCP(S₁, S₂ ,…, S_K), is defined as largest possible integer j such that S₁[1, j] = S₂[1, j] = … = S_K[1, j].

You are given an array of N strings, A₁, A₂ ,…, 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⁹+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⁵
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 question? Checkout Sample Codes for more details.