#P18134. Power Divisions
Power Divisions
Power Divisions
给定长度为 的非负整数序列 ,令
把 分成若干连续区间。若每个区间的元素和都恰好是 2 的整数次幂,则称这个划分为好划分。
求好划分的数量,对 取模。
输入格式
第一行包含整数 ,满足 。
第二行包含 个整数 ,满足 。
输出格式
输出好划分数量模 的结果。
样例
5
2 0 0 1 1
6
此时 。所有合法划分包括:
[4] [1] [1] [2] [2]
[4] [1,1] [2] [2]
[4] [1] [1] [2,2]
[4] [1,1] [2,2]
[4] [1,1,2] [2]
[4,1,1,2] [2]