Fibonacci Words
题意翻译
定义 01 串的 Fibonacci 字符序列：
$$
F(n)=
\begin{cases}
0 & \text{if } n = 0\\
1 & \text{if } n = 1\\
F(n-1) + F(n-2) & \text{if } n \geq 2
\end{cases}
$$
这里 + 表示字符串拼接。$F(n)$ 的前几项如下表所示：
| $n$ | $F(n)$ |
| :----------- | :----------- |
| 0 | 0 |
| 1 | 1 |
| 2 | 10 |
| 3 | 101 |
| 4 | 10110 |
| 5 | 10110101 |
| 6 | 1011010110110 |
| 7 | 101101011011010110101 |
| 8 | 1011010110110101101011011010110110 |
| 9 | 1011010110110101101011011010110110101101011011010110101 |
给定正整数 $n$ 和 01 串 $p$，问 $p$ 在 01 串 $F(n)$ 中出现了几次?
### 输入格式
有多组测试数据，对于每组测试数据：
第一行一个整数 $n$。
第二行一个 01 字符串 $p$。
保证 $n \leq 100$，$|p| \leq 10^5$。
### 输出格式
对于每组测试数据，输出数据编号和你的答案，保证答案不超过 $2^{63}$。
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=247&page=show_problem&problem=3895
[PDF](https://uva.onlinejudge.org/external/12/p1282.pdf)
输入输出格式
输入格式
输出格式
输入输出样例
输入样例 #1
6
10
7
10
6
01
6
101
96
10110101101101输出样例 #1
Case 1: 5
Case 2: 8
Case 3: 4
Case 4: 4
Case 5: 7540113804746346428