一条长街上竖立着一些灯柱，上面安装着 盏路灯。我们沿街建立坐标系。第 盏路灯所在的灯柱位于坐标 处。在本题的前六个子任务中（共占 85 分），任意两盏路灯不会安装在同一个灯柱上，即所有 互不相同。在最后两个子任务中，每个灯柱上至多可以有两盏路灯。
为了照亮街道，可以点亮其中一部分路灯。被点亮的第 盏路灯具有亮度 。它发光时能够从所在灯柱开始，照亮一段长度为 米的连续街道。每盏被点亮的路灯既可以转向左边，也可以转向右边。若将第 盏路灯向左照，它照亮区间 ；若向右照，则照亮区间 。
我们选择一个非空的路灯集合来照亮一段街道。如果能够将集合中的每盏路灯选择向左或向右照射，使得以下两个条件同时成立，则称该集合是经济的：
- 被照亮的区间拼接成一段连续不断的街道区间；
- 任意长度非零的区间不会被两盏或以上的路灯同时照亮。
下图展示了样例 2 中包含两盏路灯的经济子集及其照亮连续区间的方案。每盏路灯上方标注了其亮度。
:::align{center}
:::
请求出路灯的经济子集个数。输出答案对 取模的结果。
