AT_abc212_h [ABC212H] Nim Counting

[problemUrl]: https://atcoder.jp/contests/abc212/tasks/abc212_h 正の整数 $ N $ , $ K $ と長さ $ K $ の整数列 $ (A_1,\ A_2,\ \ldots,\ A_K) $ が与えられます。 高橋君と青木君が石取りゲームをすることを考えます。最初、山がいくつかあり、それぞれの山には $ 1 $ 個以上の石があります。 高橋君から始めて $ 2 $ 人は交互に以下の操作を繰り返します。 - 石が $ 1 $ つ以上残っているような山を $ 1 $ つ選ぶ。 選んだ山に $ X $ 個の石があるとき、 $ 1 $ 個以上 $ X $ 個以下の任意の個数の石をその山から取り除く。 先に操作ができなくなったプレイヤーが負けとなります。 さて、ゲームを始める前の初期状態として次のようなものを考えます。 - 山の個数を $ M $ としたとき、 $ 1\leq\ M\leq\ N $ をみたす。 - 各山にある石の個数は $ A_1,\ A_2,\ \ldots,\ A_K $ のいずれかである。 山の順番を並び替えて一致するものも区別するとしたとき、これをみたす初期状態として考えられるものは $ K+K^2+\cdots\ +K^N $ 通りあります。このうち、 $ 2 $ 人が自分が勝つために最適な行動をしたとき、高橋君が勝てるような初期状態の個数を $ 998244353 $ で割ったあまりを求めてください。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ K\