For a string $$$S$$$ of length $$$n$$$, let $$$S[a..b]$$$ denote the substring consisting of the characters from position $$$a$$$ to position $$$b$$$ (where $$$1 \leq a \leq b \leq n$$$). Also, the failure function $$$f: [0, n] \rightarrow [0, n-1]$$$ of $$$S$$$ is defined as follows.

$$$$$$ f(i) = \max( \{ 0 \} \cup \{ j \, \vert \, S[1..j] = S[i-j+1..i], \, 1 \leq j \lt i \} ) $$$$$$

The KMP automaton made using the failure function of string $$$S$$$ denotes the following kind of automaton. The automaton has $$$n+1$$$ states $$$[0..n]$$$, and for each state $$$0 \leq i \leq n$$$, there exists exactly one transition from $$$i$$$ to $$$f(i)$$$.

If a KMP automaton can be embedded on a plane, it means that if we map state $$$i$$$ to a point at $$$(i, 0)$$$ on the plane, and draw all transitions $$$i \rightarrow f(i)$$$ as arrows which do not cross the $$$x$$$-axis on the plane, it is possible to draw all $$$n+1$$$ arrows such that no arrows intersect except when they meet at endpoints.

Using an alphabet consisting of $$$C$$$ letters, find the number of strings of length $$$n$$$ whose KMP automaton can be embedded on a plane modulo $$$998\,244\,353$$$.

KMP automaton for the string $$$S = \texttt{abab}$$$

• $$$1 \leq n \leq 10^{18}$$$
• $$$1 \leq C \leq 10^{9}$$$