Description

设有一个不均匀的 $n$ 面骰子，其第 $i$ 面朝上的概率为 $\frac{a_i}{1000}$。定义事件 $A$ 为「骰子朝上的面属于集合 $\{1,2,\ldots,k\}$（$k=0$ 时集合为空集）」。对于任意子集 $I \subseteq \{1,2,\ldots,n\}$，定义事件 $B_I$ 为「骰子朝上的面属于集合 $I$」。试求在全部 $2^n$ 个事件 $B_I$ 中，满足以下独立性条件

的事件数量。

Input

第一行两个整数 $n$ 和 $k$（$1 \leq n \leq 1000,0 \leq k \leq n$）。

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 1000$），保证 $\sum_{i=1}^n a_i = 1000$。

Output

输出一行一个整数，表示答案。由于这个值可能很大，你需要输出答案对 $998244353$ 取模后的值。

Samples

4 2
200 300 200 300

4

1 1
1000

2

3 0
1 997 2

8

Note

第一组样例中满足条件的 $I$ 有 $\emptyset,\{1,3\},\{2,4\},\{1,2,3,4\}$ 四个。

第三组样例 $k = 0$，此时对于任何事件 $B_I$ 均满足 $P(A) \cdot P(B_I) = P(A \cap B_I) = 0$，满足条件的事件 $B_I$ 共有 $2^3=8$ 个。

Resources

The 23rd UESTC Programming Contest Preliminary