Заданы три строки (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).
Если какие-то из обозначений вам не знакомы, прочтите примечание.
Каждая из трех строк входных данных содержит одну непустую строку. Сумма длин строк не превышает 3·105. Каждая строка состоит только из строчных латинских букв.
Выведите 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.
abc bc cbc
3 1
abacaba abac abcd
11 2 0 0
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач