Заданы три строки (s1, s2, s3). Для каждого целого l (1 ≤ l ≤ min(|s1|, |s2|, |s3|), найдите количество троек целых чисел (i1, i2, i3) таких, что три строки sk[ik... ik + l - 1] (k = 1, 2, 3) попарно равны между собой. Все найденные числа выведите по модулю 1000000007 (109 + 7).
Если какие-то из обозначений вам не знакомы, прочтите примечание.
Выходные данные
Выведите min(|s1|, |s2|, |s3|) чисел, разделенных пробелом — ответы на задачу по модулю 1000000007 (109 + 7).
Примечание
Рассмотрим строку t = t1t2... t|t|, где ti обозначает i-й символ строки, а |t| обозначает длину строки t.
Подстрокой t[i... j] (1 ≤ i ≤ j ≤ |t|) будем называть строку titi + 1... tj.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
abc
bc
cbc
|
3 1
|
|
2
|
abacaba
abac
abcd
|
11 2 0 0
|