// Arup Guha
// 6/1/2012
// Solution to 2012 World Finals Problem D: Fibonacci Words
import java.util.*;

public class d {

	public static void main(String[] args) {

		String[] fibs = new String[30];

		fibs[0] = "0";
		fibs[1] = "1";

		// Build small cases easily.
		for (int i=2; i<fibs.length; i++)
			fibs[i] = fibs[i-1] + fibs[i-2];

		Scanner stdin = new Scanner(System.in);

		int loop = 1;
		while (stdin.hasNext()) {

			int n = stdin.nextInt();
			String s = stdin.next();

			// Just do brute force for the easy cases.
			if (n < fibs.length)
				System.out.println("Case "+loop+": "+BF(fibs[n], s));
			else {

				// Start the table.
				long[] numtimes = new long[n+1];
				for (int i=0; i<fibs.length; i++)
					numtimes[i] = BF(fibs[i], s);

				// We just need to store these two subcases, because of the repeating pattern
				// inside of the larger words. (It's kind of fractal like...)
				int gap1 = inGap(fibs[fibs.length-3], s);
				int gap2 = inGap(fibs[fibs.length-2], s);

				// We can build our solution by finding the string in both big substrings, as well
				// as within the "divide" between the two substrings (this is what gap1 and gap2 
				// are for.)
				for (int i=fibs.length; i<=n; i++) {
					if ((i-fibs.length)%2 == 0)
						numtimes[i] = numtimes[i-1] + numtimes[i-2] + gap1;
					else
						numtimes[i] = numtimes[i-1] + numtimes[i-2] + gap2;
				}
				System.out.println("Case "+loop+": "+numtimes[n]);
			}

			loop++;
		}
	}

	// Returns the number of times pattern appears in the string ss, in the gap between the two.
	// Just uses brute force.
	public static int inGap(String s, String pattern) {

		String two = s + s;
		int startIndex = s.length() - pattern.length() + 1;
		int endIndex = s.length();

		int cnt = 0;
		int first = two.indexOf(pattern, startIndex);

		while (first != -1 && first < endIndex) {
			cnt++;
			first = two.indexOf(pattern, first+1);
		}

		return cnt;
	}

	// Same here (brute force).
	public static int BF(String s, String pattern) {

		int first = s.indexOf(pattern);

		if (first == -1) return 0;

		int cnt = 0;
		while (first != -1) {
			cnt++;
			first = s.indexOf(pattern, first+1);
		}
		return cnt;
	}
}