AT_agc075_d [AGC075D] Max Prod Plus

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 < j < k \le N $ . Find 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 $ .

The input is given from Standard Input in the following format: > $ N $ $ M $ $ K $

Output the answer.

### Sample Explanation 1 The 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. ### Constraints - $ 3 \le N \le 10^9 $ - $ 1 \le M,K \le 10^4 $