Sereja and Cinema

题意翻译

### 题目描述 Sereja 的电影院有 $n$ 个座位在一个大屏幕前排成一行，在每个座位的左边和右边都有放置个人物品的凹槽，任何两个相邻的座位恰好有一个共享的凹槽，下图显示了 $n=4$ 的座位和凹槽的分布。  今天是一部名为《 Dry Hard 》的电影的首映式，所有票都卖完了。所有人会排队一个一个地进入影厅。当一个人进入影厅，他立即占据他的座位和他旁边的所有空的凹槽。如果没有空的凹槽，他会非常沮丧，然后离开。 人们不是固定不变的，所以很难预测观众进入大厅的顺序。Sereja 知道坐在某些位置的观众排在队列的位置。其他人可能排在其余任何位置。 作为一个程序员和数学家，Sereja 想知道：有多少种方式可以使得没有人沮丧而离开。因为答案很大，输出模 $1000000007$。 ### 输入格式 第一行包含一个整数 $n$。（$1\leq n\leq 10^5$） 第二行包含 $n$ 个非负整数，第 $i$ 个数表示坐在第 $i$ 个位置的观众排在队列中的位置，保证该数不超过 $n$，且不存在两个非零数相同。若第 $i$ 个数为 $0$，表示坐在第 $i$ 个位置的观众排在队列中的位置不确定。 ### 输出格式 一行一个整数，表示答案除以 $1000000007$ 后的余数。

题目描述

The cinema theater hall in Sereja's city is $ n $ seats lined up in front of one large screen. There are slots for personal possessions to the left and to the right of each seat. Any two adjacent seats have exactly one shared slot. The figure below shows the arrangement of seats and slots for $ n=4 $ . Today it's the premiere of a movie called "Dry Hard". The tickets for all the seats have been sold. There is a very strict controller at the entrance to the theater, so all $ n $ people will come into the hall one by one. As soon as a person enters a cinema hall, he immediately (momentarily) takes his seat and occupies all empty slots to the left and to the right from him. If there are no empty slots, the man gets really upset and leaves. People are not very constant, so it's hard to predict the order in which the viewers will enter the hall. For some seats, Sereja knows the number of the viewer (his number in the entering queue of the viewers) that will come and take this seat. For others, it can be any order. Being a programmer and a mathematician, Sereja wonders: how many ways are there for the people to enter the hall, such that nobody gets upset? As the number can be quite large, print it modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出格式

输入格式

The first line contains integer $ n $ $ (1<=n<=10^{5}) $ . The second line contains $ n $ integers, the $ i $ -th integer shows either the index of the person (index in the entering queue) with the ticket for the $ i $ -th seat or a $ 0 $ , if his index is not known. It is guaranteed that all positive numbers in the second line are distinct. You can assume that the index of the person who enters the cinema hall is a unique integer from 1 to $ n $ . The person who has index 1 comes first to the hall, the person who has index 2 comes second and so on.

输出格式

In a single line print the remainder after dividing the answer by number $ 1000000007 $ $ (10^{9}+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