他是一个各方面都很积极的人，除了他每天晚上都会去酒吧……

你的一个朋友是城里最著名（也是唯一）的酒吧的调酒师。城里有 $2 \cdot n + 1$ 栋房子，沿着一条长路排列，编号从 $0$ 到 $2 \cdot n$。酒吧位于编号为 $n$ 的房子里。

一个有趣的事实是，城里所有的醉汉都有同样的习惯。当然，他们离开酒吧时处于一种无法回家的状态，所以他们开始漫无目的地行走。具体来说，每个醉汉心中都有一个长度为 $n$ 的数组 $a$。在离开酒吧后的第 $i$ 秒，醉汉想要在道路上改变他的位置 $a_i$（其中 $|a_i| = 1$）。如果醉汉在第 $j$ 栋房子前，那么这次改变后他会到达第 $j + a_i$ 栋房子前。

然而，他们醉得太厉害了，以至于每一秒都有 $\frac{p}{100}$ 的概率无法移动，停留在当前位置。

如果醉汉到达了他家门前，他的家人会看到他并把他带回家。如果他本身就住在第 $n$ 栋房子里，他的家人可能会立即带走他。然而，如果在 $n$ 秒后仍未被带走，醉汉就会感到失望并睡在街上。

又有一个醉汉来到了酒吧。调酒师不知道他住在哪里，所以他假设醉汉住在每一栋房子的概率都是 $\frac{1}{2 \cdot n + 1}$。计算他的家人把他带回家的概率，结果对 $998\,244\,353$ 取模。

输入格式

第一行包含两个整数 $n$ 和 $p$ ($1 \le n \le 5000, 0 \le p \le 100$)，含义如题所述。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($|a_i| = 1$)，表示醉汉在第 $i$ 秒的意图。

输出格式

输出一个整数，即答案对 $998\,244\,353$ 取模的结果。

形式上，令 $M = 998\,244\,353$。可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数，且保证 $q$ 不能被 $M$ 整除。输出等于 $p \cdot q^{-1} \pmod M$ 的整数。换句话说，输出一个整数 $x$，满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod M$。

样例

输入 1

2 28
1 1

输出 1

702764025