나무 방향 표지판

목수가 나무 방향 표지판을 주문받았다. 표지판은 화살표 모양 판자를 아래에서 위로 쌓아 만든다. 각 판자는 바로 아래 판자와 세로로 위치를 맞춰야 하는데, 맞추는 자리는 아래 판자의 화살촉 밑변이거나 그 반대쪽 끝이고, 그 자리에 전용 나사를 박아 고정한다. 이웃한 두 판자는 반드시 겹쳐야 한다.

목수는 디자이너가 보낸 스케치를 정수 수열로 받아 적었지만 그 수열만으로는 모양이 하나로 정해지지 않는다. 게다가 원본 스케치는 이미 버렸다. 간단해 보이던 일이 큰 퍼즐이 되어 버렸다.

수열은 원소가 $1 + N$개이고 아래에서 위로 놓인 화살표 $N$개를 나타낸다. 첫 원소는 맨 아래 화살표의 왼쪽 끝 위치다. 나머지 $N$개는 아래에서 위로 각 화살촉이 시작하는 위치, 즉 $i$번째 원소는 $i$번째 화살촉 밑변의 위치다. 예를 들어 그림의 왼쪽 표지판과 오른쪽 표지판은 둘 다 2 6 5 1 4로 적을 수 있다.

판자는 바로 아래 판자와 세로로 맞춰야 하므로(아래 화살촉 밑변이거나 그 반대쪽 끝), 수열이 2 6 5 1 4 3이라면 다섯 번째 화살표는 그림의 어느 표지판에서든 1에 나사를 박아 오른쪽을 향하게 하거나 4에 나사를 박아 왼쪽을 향하게 할 수 있고, 화살촉 밑변은 3에 온다.

수열이 2 3 1이라면 두 번째 화살표는 3에 나사를 박아 왼쪽을 향하는 모양만 가능하다. 이웃한 판자가 겹쳐야 하기 때문이다.

화살촉은 모두 같은 모양이다. 디자이너는 화살촉 밑변의 위치와 맨 아래 화살표의 왼쪽 끝 위치가 모두 서로 다른 세로선 위에 있고 전체가 $1$부터 $N+1$까지의 순열을 이룬다고 알려 주었다. 그래서 목수는 자세한 내용을 빼고 순열만 적어 두었다(예를 들어 2 6 5 1 4 3).

목수가 적어 둔 수열이 주어질 때 만들 수 있는 방향 표지판의 개수를 구하라. 개수가 매우 클 수 있으므로 $2^{31} - 1 = 2147483647$로 나눈 나머지를 출력한다. 수열의 두 번째 정수는 항상 첫 번째 정수보다 크다. 맨 아래 화살표는 언제나 오른쪽을 향한다.

첫 줄에 정수 $N$이 주어진다. 둘째 줄에 $1$부터 $N+1$까지의 정수로 이루어진 순열이 주어진다. 같은 줄의 정수는 공백 하나로 구분된다.

주어진 순열로 나타낼 수 있는 서로 다른 표지판의 개수를 $2^{31} - 1 = 2147483647$로 나눈 나머지를 한 줄에 출력한다.

• $1 \le N < 2000$, 화살표의 개수