在某条道路上，有 $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$。