Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

E. Three strings

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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).

Examples

Input

abc

bc

cbc

Output

3 1

Input

abacaba

abac

abcd

Output

11 2 0 0

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).

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 12:52:34 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|