{"raw_statement":[{"iden":"problem statement","content":"Among the sequences of length $K$ consisting of integers, $A=(A_1, \\ldots, A_K)$, how many satisfy all of the conditions below?  \nFind the count modulo $998244353$.\n\n*   $0\\leq A_i \\leq M-1$ for every $i(1\\leq i\\leq K)$.\n    \n*   $\\displaystyle\\prod_{i=1}^{K} A_i \\equiv N \\pmod M$."},{"iden":"constraints","content":"*   $1 \\leq K \\leq 10^9$\n*   $0 \\leq N \\lt M \\leq 10^{12}$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$K$ $N$ $M$"},{"iden":"sample input 1","content":"2 3 6"},{"iden":"sample output 1","content":"5\n\nThe five sequences $A$ satisfying the conditions are $(1,3),(3,1),(3,3),(3,5),(5,3)$."},{"iden":"sample input 2","content":"10 0 2"},{"iden":"sample output 2","content":"1023"},{"iden":"sample input 3","content":"1000000000 20220326 1000000000000"},{"iden":"sample output 3","content":"561382653\n\nBe sure to find the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}