Dãy từ Fibonacci gồm các xâu bit được định nghĩa như sau:
$$ F(n)=\begin{cases} 0 & n=0,\\ 1 & n=1,\\ F(n-1)+F(n-2) & n\ge 2. \end{cases} $$
Ở đây $+$ biểu thị phép nối xâu. Một vài phần tử đầu tiên là:
| $n$ | $F(n)$ |
|---|---|
| $0$ | $0$ |
| $1$ | $1$ |
| $2$ | $10$ |
| $3$ | $101$ |
| $4$ | $10110$ |
| $5$ | $10110101$ |
| $6$ | $1011010110110$ |
| $7$ | $101101011011010110101$ |
| $8$ | $1011010110110101101011011010110110$ |
| $9$ | $1011010110110101101011011010110110101101011011010110101$ |
Cho một mẫu bit $p$ và một số $n$, $p$ xuất hiện bao nhiêu lần trong $F(n)$?
Dữ liệu vào
Dòng đầu tiên của mỗi bộ kiểm thử chứa số nguyên $n$ ($0 \le n \le 100$). Dòng thứ hai chứa mẫu bit $p$. Mẫu $p$ không rỗng và có độ dài không quá $100\,000$ ký tự.
Dữ liệu ra
Với mỗi bộ kiểm thử, hãy in số thứ tự của bộ kiểm thử, theo sau là số lần xuất hiện của mẫu bit $p$ trong $F(n)$. Các lần xuất hiện có thể chồng lấn nhau. Số lần xuất hiện sẽ nhỏ hơn $2^{63}$.
Ví dụ
Dữ liệu vào 1
6 10 7 10 6 01 6 101 96 10110101101101
Dữ liệu ra 1
Case 1: 5 Case 2: 8 Case 3: 4 Case 4: 4 Case 5: 7540113804746346428