OWCA Files

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/JAN20/hindi/OWCAFILE.pdf), [Bengali](http://www.codechef.com/download/translated/JAN20/bengali/OWCAFILE.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JAN20/mandarin/OWCAFILE.pdf), [Russian](http://www.codechef.com/download/translated/JAN20/russian/OWCAFILE.pdf), and [Vietnamese](http://www.codechef.com/download/translated/JAN20/vietnamese/OWCAFILE.pdf) as well. Dr.D has broken into O.W.C.A. (The Organization Without A Cool Acronym) in order to find Agent P's reports. He has already found the great vault of O.W.C.A. where Major Monogram keeps the O.W.C.A. files. Unfortunately, the vault is protected by Major Monogram's secret password. Dr.D knows that Major Monogram has always been fond of $N$ integers $A_1, A_2, \ldots, A_N$ and the password he chose is the product of $K$ of these integers modulo some prime $P$ (since the product itself might become huge and thus hard for him to remember). The integers in the product do not have to correspond to distinct elements of $A$, Major Monogram simply chose $K$ indices $i_1, i_2, \ldots, i_K$ and computed $A_{i_1} \cdot A_{i_2} \cdot \ldots \cdot A_{i_K}$ modulo $P$. With a lot of effort, Dr.D found out $P$, $K$ and $A$, but he does not know how Major Monogram chose $K$ integers from the sequence $A$. In order to get into the vault, Dr.D has created the Bruteforceinator, which will try all sequences of $K$ valid indices $i_1, i_2, \ldots, i_K$ ($N^K$ sequences in total) and for each of them, compute the product $A_{i_1} \cdot A_{i_2} \cdot \ldots \cdot A_{i_K}$ and try its remainder modulo $P$, instead of just trying all possible passwords from $0$ to $P1$. The Bruteforceinator keeps trying even after it has tried a correct password and only unlocks the vault after it tries all $N^K$ options. While the Bruteforceinator is doing its job, Dr.D is wondering how many times it will try each possible password. For each $i$ beween $0$ and $P1$ (inclusive), find the number of times the Bruteforceinator will try $i$ as the password. Since these numbers may get large, compute them modulo $998,244,353$. ### Input  The first line of the input contains three spaceseparated integers $N$, $P$ and $K$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \ldots, A_N$. ### Output Print a single line containing $P$ spaceseparated integers. For each $i$ ($1 \le i \le P$), the $i$th of these integers should be the number of times the Bruteforceinator will try $i1$ as the password, modulo $998,244,353$. ### Constraints  $1 \le N, P \le 259,431$  $P$ is a prime number  $0 \le A_i \le P1$ for each valid $i$  $0 \le K \le 10^9+9$ ### Subtasks **Subtask #1 (16 points):** $1 \le N \le 400$ **Subtask #2 (84 points):** original constraints ### Example Input ``` 6 11 3 9 8 4 3 5 3 ``` ### Example Output ``` 0 27 9 31 28 32 19 15 18 22 15 ```Author:  kmaaszraa 
Tags  kmaaszraa 
Date Added:  8122019 
Time Limit:  4 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 