Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

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-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/18/2020 20:34:02 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|