Automata Embedding

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<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 = abab$

The first line of input contains two space-separated integers $n$ and $C$, denoting the length of the string and the number of letters in the alphabet respectively.

The first line of output should contain the number of strings of length $n$ whose KMP automaton can be embedded on a plane modulo $998\, 244\, 353$.

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