You are given three strings $(*s*_{1}, *s*_{2}, *s*_{3})$. For each integer $*l*$ $(1 ≤ *l* ≤ *min*(|*s*_{1}|, |*s*_{2}|, |*s*_{3}|)$ you need to find how many triples ($*i*_{1}, *i*_{2}, *i*_{3}$) exist such that three strings $*s*_{*k*}[*i*_{*k*}... *i*_{*k*} + *l* - 1]$ $(*k* = 1, 2, 3)$ are pairwise equal. Print all found numbers modulo $1000000007 (10^{9} + 7)$.

See notes if you are not sure about some of the denotions used in the statement.

Input

First three lines contain three non-empty input strings. The sum of lengths of all strings is no more than $3·10^{5}$. All strings consist only of lowercase English letters.

Output

You need to output $*min*(|*s*_{1}|, |*s*_{2}|, |*s*_{3}|)$ numbers separated by spaces — answers for the problem modulo $1000000007 (10^{9} + 7)$.

Note

Consider a string $*t* = *t*_{1}*t*_{2}... *t*_{|*t*|}$, where $*t*_{*i*}$ denotes the $*i*$-th character of the string, and $|*t*|$ denotes the length of the string.

Then $*t*[*i*... *j*]$ $(1 ≤ *i* ≤ *j* ≤ |*t*|)$ represents the string $*t*_{*i*}*t*_{*i* + 1}... *t*_{*j*}$ (substring of $*t*$ from position $*i*$ to position $*j*$ inclusive).