#P17775. 安和昴不是罪过
安和昴不是罪过
背景
『我不是骗子。』
题目描述
昴的乐队成员又开音趴去了,所以她只能自己花六七十打车回家。突然地,她想到了一段很美妙的旋律。
因为昴是鼓手,因而旋律可以被抽象为一个零一序列。昴觉得一段旋律是美妙的,当且仅当序列中极长零连续段的数量等于极长一连续段的数量。
- 极长零连续段 定义为, 序列上 至 的所有元素均为零,且 为序列左端点或 、 为序列右端点或 ,类似地定义极长一连续段。
但这段旋律太单调了,因此昴打算设计一段精彩的旋律。昴认为一个段长为 的旋律序列 是精彩的,当且仅当可以通过若干次下述消除操作将序列删空:
- 选定 的一个美妙的连续子段 ,将其删除,并将 和 拼合起来得到新的序列。
现在昴好奇长为 的精彩旋律个数,但昴到家了,所以这个问题交给了你,请你输出该值对 取模的结果。
输入格式
第一行输入测试数据数 。
接下来 行,每行一个整数表示该组测试数据的 。
输出格式
输出 行,第 行表示第 组测试数据的答案。
5
1
2
3
4
5
0
2
4
10
22
提示
对所有数据,满足 ,。
劝我袒露真心的是你,拦下我的还是你——
真是,受够了。