import java.util.ArrayDeque;
import java.util.Stack;
import java.util.HashSet;
import java.util.ArrayList;

public class Tree
{
    static int sum;
    
    private static class TreeNode
    {
        private TreeNode left, right;
        private char data;
        private static char id = 'a';
        private int depth, height, localMax;
 
        public TreeNode(char x)
        {
            data = x;
            depth = -1;
        }
 
        public void setLeft(TreeNode n)
        {
            left = n;
        }
 
        public void setRight(TreeNode n)
        {
            right = n;        
        }
 
        public String toString()
        {
            return Character.toString(data);
        }
 
        public char value()
        {
            return data;
        }
 
        public void branch(int depth)
        {
            if(depth <= 0)
               return;
 
            this.left = new TreeNode(++id);
            this.right = new TreeNode(++id);
 
            this.left.branch(depth - 1);
            this.right.branch(depth - 1);
           
            /*
            if(this.data == 'c')
                this.right.branch(3);
            */
            
        }
 
        public void _print(String soFar)
        {
            if(this.right != null)
                this.right._print(soFar + " .. ");
 
            System.out.println(soFar + this);
            
            if(this.left != null)
                this.left._print(soFar + " .. ");
        }
        
        public void inOrder()
        {
            
            if(this.left != null)
                this.left.inOrder();                
            
            System.out.print(this + " ");
            
            if(this.right != null)
                this.right.inOrder();
        }
        
        public void preOrder()
        {
            System.out.print(this + " ");
            
            if(this.left != null)
                this.left.preOrder();
            
            if(this.right != null)
                this.right.preOrder();
        }
        
        public void postOrder()
        {
            if(this.left != null)
                this.left.postOrder();
            
            if(this.right != null)
                this.right.postOrder();
            
            System.out.print(this + " ");
        }
        
        public void levelOrder()
        {
            ArrayDeque<TreeNode> q = new ArrayDeque<TreeNode>();
            TreeNode curr;
            
            q.add(this);
            
            while( ! q.isEmpty())
            {
                curr = q.remove();
                System.out.print(curr + " ");
                
                if(curr.left != null)
                    q.add(curr.left);
                    
                if(curr.right != null)                    
                    q.add(curr.right);
            }
        }
        
        public void printDepths(String soFar)
        {
            if(this.right != null)
                this.right.printDepths(soFar + " .. ");
 
            System.out.println(soFar + this + "("+Integer.toString(depth)+")");
            
            if(this.left != null)
                this.left.printDepths(soFar + " .. ");
             
        }
        
        public void printHeights(String soFar)
        {
            if(this.right != null)
                this.right.printHeights(soFar + " .. ");
 
            System.out.println(soFar + this + "("+Integer.toString(height)+")");
            
            if(this.left != null)
                this.left.printHeights(soFar + " .. ");
             
        }
        
        public void calcDepths(int depth)
        {
            this.depth = depth;
            
            if(this.left != null)
                this.left.calcDepths(depth + 1);
                
            if(this.right != null)
                this.right.calcDepths(depth + 1);
        }
        
        public void calcHeights()
        {
            if(this.left == null && this.right == null)
            {
                this.height = 0;
                return;
            }
            
            this.left.calcHeights();
            this.right.calcHeights();
            
            this.height = 1 + Math.max(this.left.height, this.right.height);
        }
        
        public void _calcHeights()
        {
            Stack<TreeNode> s = new Stack<TreeNode>();
            HashSet<TreeNode> r = new HashSet<TreeNode>();
            
            TreeNode node = this;
            
            s.push(node);
            r.add(node);
            
            while(! s.isEmpty())
            {
                node = s.peek();
                
                TreeNode leftChild = node.left;
                TreeNode rightChild = node.right;
                
                if(leftChild == null && rightChild == null)
                {
                    node.height = 0;
                    s.pop();
                    continue;
                }
                
                if(leftChild != null && ! r.contains(leftChild))
                {
                    s.push(leftChild);
                    r.add(leftChild);
                    continue;
                }
                
                if(rightChild != null && ! r.contains(rightChild))
                {
                    s.push(rightChild);
                    r.add(rightChild);
                    continue;
                }
                
                int left = (leftChild == null) ? -1 : leftChild.height;
                int right = (rightChild == null) ? -1 : rightChild.height;
                
                node.height = 1 + Math.max(left, right);
                s.pop();
            }
        }
        
        public int maxPath()
        {
            if(this.left == null && this.right == null)
                return 0;
                
            int maxPath = 0;
            
            if(this.left != null)
                maxPath += 1 + this.left.height;
             
             if(this.right != null)
                maxPath += 1 + this.right.height;
            
            int left = this.left.maxPath();
            int right = this.right.maxPath();
            
            return Math.max(maxPath, Math.max(left,right));
        }
    }
 
    private TreeNode root;
 
    public void inOrderPrint()
    {
        root.inOrder();
    }
    
    public void preOrderPrint()
    {
        root.preOrder();
    }
    
    public void postOrderPrint()
    {
        root.postOrder();
    }
    
    public void levelOrderPrint()
    {
        root.levelOrder();
    }
 
    private Tree(char data)
    {
        root = new TreeNode(data);
    }
 
    public void print()
    {
        root._print("");
    }
   
    public void printDepths()
    {
        root.calcDepths(0);
        root.printDepths("");
    }
    
    public void printHeights()
    {
        root._calcHeights();
        root.printHeights("");
    }
    
    public int maxPath()
    {
        root._calcHeights();
        return root.maxPath();
    }
   
    public TreeNode root()
    {
        return root;
    }
 
    public Tree(int depth)
    {
        root = new TreeNode('a');
        root.branch(depth);
    }
        
    public void getPathsFromLeft(TreeNode root, String soFar,
        ArrayList<String> list)
    {
        if(root == null)
            return;
            
        if(root.right != null)    
            getPathsFromLeft(root.right, root.data + soFar, list);
            
        list.add(root.data + soFar);    
        
        if(root.left != null)
            getPathsFromLeft(root.left, root.data + soFar, list);
    }
    
    public void getPathsFromRight(TreeNode root, String soFar,
        ArrayList<String> list)
    {
        if(root == null)
            return;
        
        if(root.right != null)    
            getPathsFromRight(root.right, soFar + root.data, list);
            
        list.add(soFar + root.data);    
        
        if(root.left != null)
            getPathsFromRight(root.left, soFar + root.data, list);
    }
    
    public void printPathsFromNode(TreeNode root)
    {
        if(root == null)
            return;
            
        int counter = 0;
        
        ArrayList<String> left = new ArrayList<String>();
        getPathsFromLeft(root.left, "", left);
        
        ArrayList<String> right = new ArrayList<String>();
        getPathsFromRight(root.right, "", right);
            
        for(String r : right)
            counter++;//System.out.println(root.data + r);
            
        counter++;//System.out.println(root);    
        
        for(String s : left)
            counter++;//System.out.println(s + root.data);
            
        for(String r : right)
            for(String s : left)
                counter++;//System.out.println(s + root + r);
                
        //System.out.println(counter);
        sum += counter;
    }
    
    public void printPaths()
    {
        _printPaths(root);
    }
    
    public void _printPaths(TreeNode root)
    {
        printPathsFromNode(root);
        
        if(root.left != null)
            _printPaths(root.left);
            
        if(root.right != null)
            _printPaths(root.right);
    }
 
    public static void main(String[] args)
    {
        Tree tree = new Tree(5);
        //tree.print();
        
        /*
        System.out.println("\n\ninorder:");
        tree.inOrderPrint();
        
        System.out.println("\n\npreorder:");
        tree.preOrderPrint();
        
        System.out.println("\n\npostorder:");
        tree.postOrderPrint();
        
        System.out.println("\n\nlevelorder:");
        tree.levelOrderPrint();
        
        System.out.println("\n\ndepths");
        tree.printDepths();
        
        System.out.println("\n\nheights");
        tree.printHeights();
        
        System.out.println("\n\nmaxpath = " + tree.maxPath());
        */
        
        tree.printPaths();
        System.out.println(sum);
    }
}