ビット列からなるフィボナッチ文字列の列を次のように定義します。
$$ F(n)=\begin{cases} 0 & n=0,\\ 1 & n=1,\\ F(n-1)+F(n-2) & n\ge 2. \end{cases} $$
ここで $+$ は文字列の連結を表します。最初のいくつかの要素は次のとおりです。
| $n$ | $F(n)$ |
|---|---|
| $0$ | $0$ |
| $1$ | $1$ |
| $2$ | $10$ |
| $3$ | $101$ |
| $4$ | $10110$ |
| $5$ | $10110101$ |
| $6$ | $1011010110110$ |
| $7$ | $101101011011010110101$ |
| $8$ | $1011010110110101101011011010110110$ |
| $9$ | $1011010110110101101011011010110110101101011011010110101$ |
ビットパターン $p$ と数 $n$ が与えられたとき、$p$ は $F(n)$ に何回現れるでしょうか？
入力
各テストケースの最初の行には整数 $n$（$0 \le n \le 100$）が含まれます。2 行目にはビットパターン $p$ が含まれます。パターン $p$ は空ではなく、長さは最大 $100\,000$ 文字です。
出力
各テストケースについて、ケース番号に続けて、ビットパターン $p$ が $F(n)$ に現れる回数を出力してください。出現箇所は重なっていてもかまいません。出現回数は $2^{63}$ 未満です。
入出力例
入力 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