题目描述

点击这里查看pdf

MianKing and GreenKing are playing a game. Initially there are $K$ integers on the blackboard and a set $S$.

MianKing and GreenKing take turns to operate and MianKing will operate first.

In each operation the player can choose an integer $x$ on the blackboard which is not a Bad Number(Will be defined below), then choose an integer $y$ in $S$.

The player should guaranteed that $y\\leq x$ and if there is no y that satisfies $y\\leq x$ in the set S, the player cannot choose this $x$.

Then the player will replace $x$ with $x-y$ on the blackboard.

If a player cannot do any operations, the player loses this game.

GreenKing is a bad woman, she wants to choose a subset of size $K$ from $\\{1...n\\}$ to ensure that she can win the game(Assuming that both players are smart enough). Now you need to help her calculate how many subset of $\\{1...n\\}$ satisfies the above conditions.

The answer may be very large, so you only need to output answer mod $998244353$.

We call a number is a Bad Number, if and only if it has an even number of 1 in the binary representation.

For example, $0,3,996$ are all Bad Numbers and $1,7$ are not Bad Numbers.

输入格式

The first line has three integers $n,K,|S|$

The second line has $|S|$ distinct integers denotes the set $S$.

$1\\leq n\\leq 10^{18}$

$1\\leq K\\leq min(n,100)$

$\\forall x \\in S, 1\\leq x\\leq 20$

$|S|>0$

输出格式

Output the answer mod $998244353$.

样例

5 2 1 
2 

6 

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

896262428 

提示

Form 2020ICPC济南站