分数: 600 点
问题陈述
给定的是正整数 N, K,以及一系列 K 整数 (A_1, A_2, \ldots, A_K).
高桥和青木将玩石头游戏。最初,有一些石头堆,每堆石头都包含一个或多个石头。玩家轮流进行以下操作,高桥先进行。
- 选择剩余一颗或多颗石头的堆。移除之间任意数量的石头 1 和 X (含)来自该堆,其中 X 是剩余的棋子数量。
首先无法执行操作的玩家失败。
现在,考虑满足以下条件的棋子的初始排列。
- 1\leq M\leq N 成立,其中 M 是石头堆的数量。
- 每堆中的石头数量为以下之一: A_1, A_2, \ldots, A_K.
假设堆是有序的,有 K+K^2+\cdots +K^N 石头的初始排列。其中,求数,取模 998244353,假设两名选手都发挥最佳状态,导致高桥获胜的安排。
约束
- 1 \leq N \leq 2\times 10^5
- 1 \leq K < 2^{16}
- 1 \leq A_i < 2^{16}
- 全部 A_i 是不同的。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 \ldots A_K
输出
打印答案。
样本输入 1
2 2 1 2
示例输出 1
4
棋子有六种可能的初始排列: (1), (2), (1,1), (1,2), (2,1),和 (2,2).
高桥对其中四人制定了制胜策略: (1), (2), (1,2),和 (2,1),青木对另外两个人有制胜策略。因此,我们应该打印 4.
示例输入 2
100 3 3 5 7
示例输出 2
112184936
一定要找到计数模数 998244353.