Informatica Online Judge

  던전 탐색 [1591 / 0637]

Time Limit(Test case) : 5000 (ms)
Number of users who solved : 6   Total Tried : 10


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (14069 유재민)]

Background

경곽이는 최근에 1인용 RPG 게임에 빠져있다. 이 게임은 수동 저장을 하면서 진행한다.
경곽이는 몬스터들을 잡으면서 경험치를 쌓기 위해 던전을 자주 간다.
이 게임에 존재하는 모든 던전들은 공통적인 특징을 가지고 있다.

첫째로, 던전 내에 있는 모든 장소를 공략해야 던전을 클리어할 수 있다.
둘째로, 입구와 출구가 같아서 던전을 클리어하면 다시 들어왔던 입구로 나와야 한다.
셋째로, 던전에서 임의의 두 장소를 지나는 경로가 하나로 유일하다.

경곽이는 불의의 상황으로 데이터가 날아가는 것을 막기 위해 던전에서 종종 수동 저장을 한다.
그러나 게임에 빠져 있으면 데이터를 저장하는 것을 잊어버리기 때문에 경곽이는 던전에서 막다른 길이 나와 다시 돌아가야 할 경우에만 저장하게 되었다.

경곽이는 어느 날 미니맵이 제공되지 않는 던전에 들어가게 되었다. 경곽이는 우수법(右手法)을 사용하면 던전의 모든 장소를 방문하고 나올 수 있다는 것을 깨닫고 효율적으로 던전을 클리어할 수 있었다. 경곽이는 던전을 클리어 한 뒤 이 던전이 어떤 형태를 가졌는지가 궁금해졌다. 하지만 던전에 다시 들어가 지도를 직접 작성하기에는 귀찮기도 하고 시간이 아까웠기에 다른 방법으로 던전의 형태를 알 방법이 없을지 고민하게 되었다.

다행히 경곽이는 던전을 공략하면서 세이브를 한 시간기록을 볼 수 있었다. 경곽이는 숙련된 게이머이기 때문에 던전 내에 있는 모든 장소를 T 시간 만에 공략한다. 또 한 번 공략한 장소에는 더는 몬스터가 나타나지 않기 때문에 매우 빠르게 이동할 수 있다.

이 정보를 가지고 경곽이가 클리어한 던전이 가질 수 있는 형태가 몇 가지인지 구해서 경곽이에게 알려주자!

Input

첫 줄에 문자열의 길이 N이 주어진다. (1≤N≤100)
둘째 줄에 길이 N의 문자열이 주어진다.
던전에 들어간 시점부터 나온 시점까지 T 시간 마다 데이터의 저장 여부가 0과 1로 구분되어 나타난다.
데이터를 저장했으면 1, 저장하지 않았으면 0이다.

[SubTask Info]
#1 (25%) : 1 ≤ N ≤ 10
#2 (75%) : 1 ≤ N ≤ 100

Output

던전이 가질 수 있는 형태의 가짓수를 출력한다.
수가 너무 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

IO Example

입력
4
0011

출력
2


다음의 2가지가 가능하다.





Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]