피보나치 단어

피보나치 단어 수열 $F(n)$은 다음과 같이 정의된다. 여기서 $+$는 두 문자열을 이어 붙이는 것을 뜻한다. $F(0)$은 문자열 0, $F(1)$은 문자열 1이고, $n \ge 2$에 대해 $F(n) = F(n-1) + F(n-2)$이다.

처음 몇 항은 다음과 같다.

비트 패턴 $p$와 정수 $n$이 주어졌을 때, $F(n)$ 안에 $p$가 몇 번 나타나는지 세는 프로그램을 작성하여라. 이때 나타나는 위치는 서로 겹쳐도 된다.

입력은 여러 개의 테스트 케이스로 이루어지며, 파일의 끝까지 계속된다.

각 테스트 케이스는 두 줄로 주어진다. 첫째 줄에는 정수 $n$이 주어진다 ($0 \le n \le 100$). 둘째 줄에는 비트 패턴 $p$가 주어진다. $p$는 비어 있지 않은 문자열이며, 길이는 최대 $100\,000$이다.

각 테스트 케이스마다 한 줄씩 Case x: k 형식으로 출력한다. 여기서 $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $k$는 $F(n)$ 안에서 비트 패턴 $p$가 (겹침을 허용하여) 나타나는 횟수이다. 이 값은 항상 $2^{63}$보다 작음이 보장된다.