원형 자전거 거치대의 야간 배치

문제

공유 자전거 관리소에는 N개의 거치 칸이 원형으로 놓여 있다. 칸에는 시계 방향으로 1번부터 N번까지 번호가 붙어 있으며, N번 칸 다음에는 다시 1번 칸이 나온다. 관리소는 야간 정비를 마친 자전거 일부를 이 거치대에 배치하려고 한다. 각 칸에는 자전거를 최대 한 대 놓을 수 있고, 칸마다 자전거를 놓을 수 있는지 여부가 미리 정해져 있다. 사용 가능한 칸이라고 해서 반드시 자전거를 놓아야 하는 것은 아니다. 사용 불가능한 칸에는 자전거를 놓을 수 없지만, 그 칸이 원형 거치대에서 사라지는 것은 아니다. 예를 들어 어떤 칸이 사용 불가능하더라도 그 양옆 칸이 새롭게 이웃하게 되지는 않는다. 이웃 관계는 처음 부여된 번호에 의해서만 정해진다. 번호 차이가 1인 두 칸은 이웃하고, 추가로 1번 칸과 N번 칸도 서로 이웃한다. 야간 점검 장비가 자전거 사이를 통과할 수 있도록, 서로 이웃한 두 칸에 자전거를 동시에 놓는 배치는 허용하지 않는다. 또한 관리소는 실제로 자전거를 배치하는 경우만 세려고 하므로 적어도 한 칸에는 자전거를 놓아야 한다. 배치할 자전거의 수에는 그 밖의 제한이 없고, 필요한 만큼 자전거를 사용할 수 있다. 자전거 자체는 서로 구별하지 않는다. 두 배치에서 자전거가 놓인 칸의 집합이 같으면 같은 배치이고, 하나라도 다른 칸이 있으면 서로 다른 배치이다. 거치대를 회전했을 때 모양이 같아 보이더라도 칸 번호가 다르면 다른 배치로 센다. 주어진 사용 가능 상태를 만족하는 배치의 수를 구한다. 배치의 수가 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다. 사용할 수 있는 칸이 없어 유효한 배치가 하나도 없다면 0을 출력한다.

입력

첫째 줄에 정수 N이 주어진다. 3≤N≤200,000이다.
둘째 줄에 길이가 N인 문자열 S가 주어진다. S는 문자 0과 1로만 이루어진다. S의 i번째 문자가 1이면 i번 칸을 사용할 수 있고, 0이면 사용할 수 없다.

출력

조건을 만족하는 비어 있지 않은 배치의 수를 1,000,000,007로 나눈 나머지를 한 줄에 출력한다.

4
1111

6

5
10101

5

3
000

0

출처: Devin.KR 자체 제작