7236: Make It Square

Luluu is a “Square” magician from Eorzea. “Square” magicians are experts to use “Square” spells.

Every spell can be represented as a non-empty string containing only lower-case English characters. The “Square” spells are those of even length which the first half is identical to the second half. For example, abcabc and aaaa are “Square” spells, while aaa and abcabd are not.

Today, Luluu found a powerful “Square” spell from Grimoire, but unfortunately, the book page is damaged, so some parts of the spell are not readable anymore.

More specifically, the original “Square” spell is of the format p+s+q+t, where $s$ and $t$ are two constant strings, but $p$ and q are the two unreadable parts of the spell. From some investigation, Luluu believes $p$ and q should be of the same length that doesn't exceeds m.

Now, Luluu asks your help to calculate the number of all possible original “Square” spells. Could you help this poor magician?

The first line contains a single integer $m$ (1≤m≤10^6), the second line contains a string $s$ and the third line contains a string t.
It is guaranteed that the length of s and $t$ don't exceed 10^6.

Output $m$ integers in a single line, the k-th of which indicates the number of possible original “Square” spells when the length of p and the length of q are both k.
The answers could be large, so you should output them modulo $353$.

3
abbab
b

0 1 26

For the first sample case:
When the length of p and q are both 1, there is no valid solution to make p+s+q+t a “Square” spell.
When the length of p and q are both $2$, there is only one valid solution, which is (p=ab, $=$ab). The “Square” spell is ababbababb.
When the length of p and q are both $3$, there are $26$ valid solutions, which are of format (p=ab?, q=?ab), where ? could be any single lower-case English character.