{"problem":{"name":"Max Prod Plus","description":{"content":"For a length-$N$ sequence of positive integers $A=(A_1,A_2,\\dots,A_N)$, define $f(A)$ as follows: *   The maximum value of $A_iA_j + A_k$ over all triples of integers $(i,j,k)$ satisfying $1 \\le i < ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc075_d"},"statements":[{"statement_type":"Markdown","content":"For a length-$N$ sequence of positive integers $A=(A_1,A_2,\\dots,A_N)$, define $f(A)$ as follows:\n\n*   The maximum value of $A_iA_j + A_k$ over all triples of integers $(i,j,k)$ satisfying $1 \\le i < j < k \\le N$.\n\nFind the number, modulo $998244353$, of length-$N$ sequences $A$ of positive integers with all elements between $1$ and $M$, inclusive, such that $f(A) \\le K$.\n\n## Constraints\n\n*   $3 \\le N \\le 10^9$\n*   $1 \\le M,K \\le 10^4$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc075_d","tags":[],"sample_group":[["3 5 4","9\n\nThe sequences satisfying the condition are $(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,1,3),(1,2,2),(2,1,2),(1,3,1),(3,1,1)$, which is nine sequences."],["4 5 7","66"],["123 456 789","436486661"],["1000000000 10000 10000","855626126"]],"created_at":"2026-03-03 11:01:13"}}