在某条道路上，有 n 盏灯排成一排，它们有的是开着的，有的是关着的。

由于天马上就要亮了，上级给了你一个任务：把所有的灯都关掉。

只不过，这些灯都比较智能，不会被轻易关掉。它们的开或关遵循如下规则：

• 每一步只能开或关一盏灯。
• 编号为 1 的灯可以随意开或关。
• 如果编号为 1, 2, \cdots,k-1 的灯都关上了了，并且编号为 k 的灯在开着，我们可以随意开或关第 k+1 盏灯。

在关灯之前，请你计算：至少要多少步才能关上所有灯？

第 1 行一个整数 n，表示灯的个数。

第 2 行有 n 个整数，如果第 i 个整数 O_i=0，表示第 i 个盏灯初始的时候是关着的；如果 O_i=1，表示第 i 盏灯初始的时候是开着的。

共一行一个整数，表示最少需要多少步才能关上所有灯。

结果可能很大，你只需要输出其对10^9+7取模的结果即可

【输出解释】

• 初始状态 1010；
• 第 1 步 1110；
• 第 2 步 0110；
• 第 3 步 0100；
• 第 4 步 1100；
• 第 5 步 1000；
• 第 6 步 0000。

数据范围及约定

• 对于 40\% 的数据，n \le 30；
• 对于 70\% 的数据，n \le 300；
• 对于 100\% 的数据，n \le 1000。

luogu