// Program to print recursively all binary strings
// of length n of the strings "A" and "Z"

import java.io.*;

class Day{

static final int MAXN=100;
static int [] count = new int[MAXN];
static int n;
static String [] buf = new String[MAXN];

static void printbuf(){
        System.out.print("buf is: ");
        for (int k=0;k<n;++k) 
            System.out.print(buf[k]);
        System.out.println();
}

static void bin(int i) {
        ++count[i];


	if (i == 0) { 
		printbuf();
	}
	else {
		buf[n-i] = "A"; 
                bin(i - 1);

		buf[n-i] = "Z"; 
                bin(i - 1);
	}
}

  public static void main (String [] args) {

   int k,sum=0 ; 
   n = Integer.parseInt(args[0]);
   for (k=0;k<n;++k) count[k]=0;

   bin(n);
        
   for (k=0;k<n;++k) {
            sum += count[k];
            System.out.print(k+": "+count[k]+" ");
        };
        System.out.println(" sum= "+sum);
} // main


}