Farmer Nhoj는 베시를 아무것도 없는 곳 한가운데에 내려놓았다! 시간 \(t=0\)일 때 베시는 무한한 수직선 위의 \(x=0\)에 있다. 베시는 출구를 찾기 위해 매초 왼쪽이나 오른쪽으로 한 칸씩 다급하게 이동한다. 하지만 실제로 출구는 없었고, \(T\)초가 지난 뒤 베시는 지치고 체념한 채 \(x=0\)으로 돌아온다.

Farmer Nhoj는 베시의 이동 경로를 추적하려고 하지만, 베시가 \(x=0.5,1.5,2.5,\dots,(N-1).5\)를 각각 몇 번 통과했는지만 알고 있다. 이 횟수는 배열 \(A_0,A_1,\dots,A_{N-1}\)로 주어진다. \((1 \le N \le 100,000,\ 1 \le A_i \le 1,000,000)\) 베시는 \(x>N\)이나 \(x<0\)인 위치에는 도달하지 않는다.

베시의 경로는 L과 R로 이루어진 길이 \(T=\sum_{i=0}^{N-1}A_i\)인 문자열로 나타낼 수 있다. \(i\)번째 문자는 \(i\)번째 초에 베시가 이동한 방향을 나타낸다. 방향을 바꾼 횟수는 문자열에 나타나는 LR의 개수와 RL의 개수를 더한 값으로 정의한다.

배열 \(A\)와 일치하는 베시의 경로 중에서 방향을 바꾼 횟수가 최소인 경로의 개수를 구하여라. 유효한 경로가 하나 이상 존재함이 보장된다.

입력

첫째 줄에 정수 \(N\)이 주어진다.

둘째 줄에 \(A_0,A_1,\dots,A_{N-1}\)이 공백으로 구분되어 주어진다.

출력

조건을 만족하면서 방향을 바꾼 횟수가 최소인 경로의 개수를 \(1,000,000,007\)로 나눈 나머지를 출력한다.

예제 입력 1

2
4 6

예제 출력 1

2

예제 설명 1

베시는 방향을 최소 \(5\)번 바꾸어야 한다. 방향을 정확히 \(5\)번 바꾸는 경로는 다음 두 가지이다.

RRLRLLRRLL
RRLLRRLRLL

출처

USACO 2023 January Contest, Gold, Problem 3. Moo Route