E. Три строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Заданы три строки (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).

Примеры
Входные данные
abc
bc
cbc
Выходные данные
3 1
Входные данные
abacaba
abac
abcd
Выходные данные
11 2 0 0
Примечание

Рассмотрим строку t = t1t2... t|t|, где ti обозначает i-й символ строки, а |t| обозначает длину строки t.

Подстрокой t[i... j] (1 ≤ i ≤ j ≤ |t|) будем называть строку titi + 1... tj.