题目描述

Y 同学要从 $N$ 个按顺序排列的部门中招聘恰好 $K$ 名成员。第 $i$ 个部门有 $A_i$ 名候选人，同一部门内的候选人互不相同。Y 同学可以从一个部门中选择任意数量的人，也可以一个都不选。

为了避免相邻部门同时被抽调造成工作交接困难，若某个部门至少被选择了一名候选人，则它的相邻部门不能再选择任何人。换句话说，所有非空选择部门在序列上不能相邻。选择方案由具体候选人集合决定，而不仅仅由每个部门选择人数决定。

请你计算恰好选出 $K$ 名成员的方案数，并输出对 $998244353$ 取模后的结果。

输入格式

第一行包含两个整数 $N,K$。

第二行包含 $N$ 个整数 $A_1,A_2,\dots,A_N$。

输出格式

输出一行一个整数，表示方案数对 $998244353$ 取模后的结果。

样例

样例输入 #1

3 2
2 3 2

样例输出 #1

9

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le N\le1000$，$1\le K\le80$，$1\le A_i\le10^9$。

特殊性质 A：保证所有 $A_i=1$。 特殊性质 B：保证 $K=1$。