암호문

모리아티는 죽었지만 그를 따르는 사람은 여전히 많이 남아 있다. 어제 그중 한 명이 중요한 메시지를 들고 도시에 도착했다. 왓슨과 홈즈는 그를 붙잡아 주머니에서 편지를 찾아내고 심문을 시작했다.

심문으로 다음 사실을 알아냈다. 편지에는 모리아티가 죽기 전에 실행하지 못한 음흉한 계획이 암호화되어 적혀 있다. 모리아티는 모든 정보를 0과 1로만 이루어진 이진 코드 문자열로 보관하는 습관이 있었다. 그는 계획을 설명하는 메시지를 다음 방식으로 암호화했다. 이진 문자열을 같은 문자가 연속으로 이어지는 최대 길이의 묶음으로 나눈 뒤, 각 묶음을 그 문자와 묶음 안의 개수로 바꾼다. 예를 들어 111은 13이 되고, 0000000000은 010이 된다. 따라서 11100은 1302가 되고, 00000000001은 01011이 된다.

암호화된 계획 문자열도 이진 문자열이라는 사실이 밝혀졌다. 교수는 바로 그 문자열을 편지에 담아 보냈다.

이 밖에 알려진 것은 없다. 셜록은 무엇이 암호화되었는지 알고 싶어 한다. 하지만 정확히 복원하기는 어렵다. 그래서 그는 왓슨과 홈즈가 가로챈 문자열로 암호화될 수 있는 원래 메시지의 개수라도 알고 싶어 한다. 이 값은 매우 클 수 있으므로 $1\,000\,000\,007$로 나눈 나머지만 구하면 된다.

첫 줄에 가로챈 메시지의 길이를 나타내는 정수 $n$이 주어진다 ($1 \le n \le 100\,000$).

둘째 줄에 길이가 $n$이고 0과 1로만 이루어진 메시지가 주어진다.

가능한 원래 메시지의 개수를 $1\,000\,000\,007$로 나눈 나머지를 한 줄에 출력한다.