MianKing 和 GreenKing 正在玩一个游戏。初始时，黑板上有 $K$ 个整数，以及一个集合 $S$。

MianKing 和 GreenKing 轮流进行操作，MianKing 先手。

在每次操作中，玩家可以选择黑板上的一个整数 $x$（该数不能是“坏数”，定义见下文），然后选择集合 $S$ 中的一个整数 $y$。

玩家必须保证 $y \le x$。如果集合 $S$ 中不存在满足 $y \le x$ 的 $y$，则玩家不能选择该 $x$。

随后，玩家将黑板上的 $x$ 替换为 $x - y$。

如果一名玩家无法进行任何操作，则该玩家输掉游戏。

GreenKing 是一个坏女人，她想要从 $\{1 \dots n\}$ 中选择一个大小为 $K$ 的子集，以确保她能赢得游戏（假设双方都足够聪明）。现在你需要帮她计算有多少个 $\{1 \dots n\}$ 的子集满足上述条件。

答案可能非常大，你只需要输出答案对 $998244353$ 取模的结果。

如果一个数的二进制表示中 $1$ 的个数为偶数，我们称该数为“坏数”。例如，$0, 3, 996$ 都是坏数，而 $1, 7$ 不是坏数。

输入格式

第一行包含三个整数 $n, K, |S|$。

第二行包含 $|S|$ 个不同的整数，表示集合 $S$。

$1 \le n \le 10^{18}$ $1 \le K \le \min(n, 100)$ $\forall x \in S, 1 \le x \le 20$ $|S| > 0$

输出格式

输出答案对 $998244353$ 取模的结果。

样例

样例输入 1

5 2 1
2

样例输出 1

6

样例输入 2

1000 100 10
1 2 3 4 5 6 7 8 10 11

样例输出 2

896262428