← 返回题目列表

Codeforces · 380/D

D. 塞雷贾和电影院

中文机器翻译题面 查看原题

塞雷贾市的电影院大厅有n个座位,在一个大屏幕前排成一排。每个座位的左侧和右侧都有用于存放个人物品的槽位。任意两个相邻的座位恰好有一个共享位置。下图显示了 n = 4 时的座位和槽位排列。

今天是一部名为“干硬”的电影的首映。所有座位的票都已售完。剧院入口处有一个非常严格的管制员,所以所有n个人都会一一进入大厅。一个人一进入电影院,他就立即(瞬间)入座并占据他左右两侧的所有空位。如果没有空位,该男子就会非常沮丧并离开。

人流不是很恒定,因此很难预测观众进入大厅的顺序。对于某些座位,Sereja 知道将前来占据该座位的观众人数(他在观众进入队列中的号码)。对于其他人来说,它可以是任何顺序。

作为一名程序员和数学家,Sereja 想知道:有多少种方式可以让人们进入大厅,从而不会有人感到不安?由于数字可能非常大,因此将其打印为对 1000000007 (109 + 7) 取模。

输入

第一行包含整数 n (1 ≤ n ≤ 105)。第二行包含 n 个整数,第 i 个整数显示持有第 i 个座位票的人的索引(进入队列中的索引)或 0(如果他的索引未知)。保证第二行中的所有正数都是不同的。

你可以假设进入电影院的人的索引是从1到n的唯一整数。索引为 1 的人首先进入大厅,索引为 2 的人第二次进入大厅,依此类推。

输出

在一行中打印答案除以数字 1000000007 (109 + 7) 后的余数。

示例

输入 #1

11
0 0 0 0 0 0 0 0 0 0 0

输出 #1

1024

输入 #2

6
0 3 1 0 0 0

输出 #2

3