Zawad and Index Sum
All submissions for this problem are available.### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK107/hindi/IDXSUM.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK107/mandarin/IDXSUM.pdf), [Russian](http://www.codechef.com/download/translated/COOK107/russian/IDXSUM.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK107/vietnamese/IDXSUM.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK107/bengali/IDXSUM.pdf) as well. Zawad is a rare competitive programmer — he takes his studies seriously. One day, while studying in a library, he found a pattern $P$ in a century old book. The pattern is a string of lowercase English letters, with length $M$. Since Zawad is a curious boy, he started experimenting with the pattern. In one experiment, Zawad considers all $26^N$ strings with length $N$ that contain only lowercase English letters. The strings are numbered $0$ through $26^N - 1$ in lexicographical order. For each valid $i$, let $C_i$ be the length of the longest prefix of $P$ which is also a suffix of the $i$-th of these strings ($0 \le C_i \le M$). For each integer $k$ between $0$ and $M$ inclusive, let $S_k$ denote the sum of all valid indices $i$ such that $C_i = k$. Zawad wants to know all these sums, but since they could be huge, it is enough to compute them modulo $998,244,353$. Since Zawad is a bit busy at the library, he is asking for your help. Can you find the sums and earn Zawad's respect? ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains two space-separated integers $M$ and $N$. - The second line contains a single string $P$ with length $M$. ### Output For each test case, print a single line containing $M+1$ space-separated integers $S_0, S_1, \ldots, S_M$ — the sums modulo $998,244,353$. ### Constraints - $1 \le T \le 5$ - $1 \le M \le 10^5$ - $M \le N \le 10^6$ - $P$ contains only lowercase English letters ### Example Input ``` 2 1 1 a 3 5 nan ``` ### Example Output ``` 325 0 555099525 502507217 596119576 22936464 ```
|Tags||cook-off, cook107, solaimanope|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.