레이팅 미적용농부 뇌즈가 베시를 아무것도 없는 허허벌판에 떨어뜨렸다! 시각 \(t=0\)에 베시는 무한한 수직선 위의 \(x=0\)에 있다. 그녀는 매초 왼쪽 또는 오른쪽으로 \(1\) 단위씩 움직이며 필사적으로 출구를 찾는다. 그러나 사실 출구는 없으며, \(T\)초 후 베시는 지치고 체념한 채 \(x=0\)으로 돌아온다.
농부 뇌즈는 베시를 추적하려 하지만, 베시가 \(x=.5, 1.5, 2.5, \ldots, (N-1).5\)를 각각 몇 번 지나갔는지만 알고 있으며, 이는 배열 \(A_0,A_1,\dots,A_{N-1}\) (\(1\leq N \leq 10^5\), \(1 \leq A_i \leq 10^6\))로 주어진다. 베시는 결코 \(x>N\)이나 \(x<0\)에 도달하지 않는다.
구체적으로, 베시의 경로는 \(T = \sum_{i=0}^{N-1} A_i\)개의 \(L\)과 \(R\)로 이루어진 문자열로 나타낼 수 있으며, \(i\)번째 문자는 \(i\)번째 초 동안 베시가 움직이는 방향을 나타낸다. 방향 전환 횟수는 \(LR\)의 출현 횟수와 \(RL\)의 출현 횟수의 합으로 정의된다.
\(A\)와 일치하면서 방향 전환 횟수를 최소화하는, 베시가 지났을 수 있는 경로의 수를 세도록 농부 뇌즈를 도와주자. 유효한 경로가 적어도 하나 존재함이 보장된다.
Problem credits: Brandon Wang, Claire Zhang, and Benjamin Qi
채점 방식
- 입력 2-4: \(N\le 2\) 그리고 \(\max(A_i)\le 10^3\)
- 입력 5-7: \(N\le 2\)
- 입력 8-11: \(\max(A_i)\le 10^3\)
- 입력 12-21: 추가 제약이 없다.
Problem credits: Brandon Wang, Claire Zhang, and Benjamin Qi
첫째 줄에 \(N\)이 주어진다. 둘째 줄에 \(A_0,A_1,\dots,A_{N-1}\)이 주어진다.
베시가 지났을 수 있는 경로의 수를 \(10^9+7\)로 나눈 나머지를 출력한다.
2
4 62Bessie must change direction at least 5 times. There are two routes
corresponding to Bessie changing direction exactly 5 times:
RRLRLLRRLL
RRLLRRLRLL