#P17997. Pluses and Minuses
Pluses and Minuses
Pluses and Minuses
题目描述
Misha 在笔记本里写下了若干个他认为“美丽”的非负整数。
一个仅由 + 和 - 组成的字符串被称为平衡串,当且仅当:
- 其中
+和-的数量相等; - 字符串末尾连续出现的
-的数量是美丽数。
末尾连续负号的数量必须是恰好这个数;若最后一个字符为 +,则末尾负号数量为 。这里不要求任意前缀中正号数量不少于负号数量。
请分别求长度为 的平衡串数量,答案对 取模。
输入格式
第一行两个整数 ,。
第二行包含 个互不相同的整数,均属于 ,表示所有美丽数。
输出格式
输出 行,第 行表示长度为 的平衡串数量模 的结果。
样例 1
输入
5 3
1 2 3
输出
1
3
10
34
120