题目描述

给定两个数 $N,K$,以及一个长度为 $K$ 的整数数组 $(A_i,A_2...A_K)$。

两个人玩 Nim 游戏。

现在通过以下方式生成一个游戏：

任意选择一个 $1\le M\le N$，$M$ 表示石子堆数。

对于每一堆，其石子数是 $A$ 中任意一个数。

对于 $\sum_{i=1}^N K^i$ 种游戏，求先手获胜的游戏数，答案对 $998244353$ 取模。

输入格式

第一行两个数 $N,K$。

输出格式

一行一个数，表示答案。

数据范围

• $1\le N\le 2\times 10^5$

• $1\le A_i,K<2^{16}$。

• $A_i$ 两两不同。

样例 $1$ 解释

总共有 $6$ 种可能的游戏 $(1),(2),(1,2),(2,1),(1,1),(2,2)$。

其中先手赢的是 $(1),(2),(1,2),(2,1)$,一共 $4$ 种情况。

$\textsf{\textbf{Translated by @\color{5eb95e}nr0728}}.$