{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $3 \\le N \\le 10^9$\n*   $1 \\le M,K \\le 10^4$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$ $K$"},{"iden":"sample input 1","content":"3 5 4"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"4 5 7"},{"iden":"sample output 2","content":"66"},{"iden":"sample input 3","content":"123 456 789"},{"iden":"sample output 3","content":"436486661"},{"iden":"sample input 4","content":"1000000000 10000 10000"},{"iden":"sample output 4","content":"855626126"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}