← 返回题目列表

AtCoder · abc212_h

H. 尼姆计数

中文机器翻译题面 查看原题

分数: 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.