给你三个字符串(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)。
示例
输入 #1
abc bc cbc
输出 #1
3 1
输入 #2
abacaba abac abcd
输出 #2
11 2 0 0
注意
考虑一个字符串 t = t1t2... t|t|,其中 ti 表示字符串的第 i 个字符,|t| 表示该字符串的第 i 个字符。表示字符串的长度。
则 t[i... j] (1 ≤ i ≤ j ≤ |t|) 表示字符串 titi + 1... tj (t 从位置 i 到位置 j 的子串)。