小 Z 喜欢做题的时候随机游走。

题目描述

小 Z 初始在 $0$ 号位置，每次会向左或右走一个单位坐标。

具体地，他的行走轨迹可以看成是一个长度为 $n$ 的序列 $a_i$，表示第 $i$ 个时刻移动方向为 $a_i$。保证 $|a_i|=1$，其中 $a_i=1$ 表示向正方向移动 $1$ 单位长度，$a_i=-1$ 表示向负方向移动 $1$ 单位长度。

因为神力的存在，所以小 Z 有 $\frac{p}{100}$ 的概率可能在第 $i$ 个时刻突然不想移动了，即不进行这个时刻的移动操作。

现在小 Z 想知道，对于位置 $i\in [-n,n]\cap \mathbb{Z}$，他经过这个位置的概率，对 $10^9+7$ 取模。

输入格式

第一行，两个整数 $n,p$ 表示移动序列长度为 $n$ 以及停下概率为 $\frac{p}{100}$。

第二行，$n$ 个整数 $a_i$ 表示移动序列。

输出格式

一行，$2n+1$ 个非负整数表示答案。

样例 #1

样例输入 #1

5 83
1 -1 -1 1 1

样例输出 #1

0 0 0 710859005 390982003 1 135049706 506522154 13802205 0 0

样例 #2

样例输入 #2

见下发文件 god2.in。

该测试点满足 $n\le 300$。

god2.in

样例输出 #2

见下发文件 god2.ans。

god2.ans

提示

对于所有数据满足，$1\le n\le 5000$，$0\le p\le 100$，$a_i\in \{-1,1\}$。

• 特殊性质 A：$p=50$；
• 特殊性质 B：$p=100$；
• 特殊性质 C：$p=0$；
• 特殊性质 D：$a_i=-1$；
• 特殊性质 E：保证存在位置 $p$，满足 $\forall i\in [1,p]\cup \mathbb{Z}，a_i=-1$，$\forall i\in (p,n]\cup \mathbb{Z}，a_i=1$。