32461번 - 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}$

노트