{"problem":{"name":"Ex - Product Modulo 2","description":{"content":"Among the sequences of length $K$ consisting of integers, $A=(A_1, \\ldots, A_K)$, how many satisfy all of the conditions below?   Find the count modulo $998244353$. *   $0\\leq A_i \\leq M-1$ for every","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc245_h"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $1 \\leq K \\leq 10^9$\n*   $0 \\leq N \\lt M \\leq 10^{12}$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$K$ $N$ $M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc245_h","tags":[],"sample_group":[["2 3 6","5\n\nThe five sequences $A$ satisfying the conditions are $(1,3),(3,1),(3,3),(3,5),(5,3)$."],["10 0 2","1023"],["1000000000 20220326 1000000000000","561382653\n\nBe sure to find the count modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}