DP - 1:Number of Balanced BTs

// public class Solution 
// {
//     public static int balancedTreesOfHeightH(int height)
        
//     {  int mod = (int)Math.pow(10, 9) + 7;
// 		return balancedTreesOfHeightH(height, mod);
//     }
//      public static int balancedTreesOfHeightH(int height,int mod){
//         if(height==0 || height==1)
//             return 1;
//         int x=balancedTreesOfHeightH(height-1,mod);
//         int y=balancedTreesOfHeightH(height-2,mod);
//         long a=(long)x*x;
//         long b=(long)x*y*2;
//         int resa=(int)(a%mod);
//         int resb=(int)(b%mod);
//         return (resa+resb)%mod;
        
//     }



//     }
    
 public class Solution 
{
    public static int balancedTreesOfHeightH(int height)
    {
        int storage[]=new int[height+1];
        for(int i=0;i<storage.length;i++)
        {
            storage[i]=-1;
        }
        int mod=(int)Math.pow(10,9)+7;
        return balancedOfTreesHeightH(storage,height,mod);
    }
    private static int balancedOfTreesHeightH(int storage[],int height,int mod){
        if(height==0 || height==1)
        {
            storage[height]=1;
            return 1;
        }
        if(storage[height]!=-1)
            return storage[height];
        int x=balancedOfTreesHeightH(storage,height-1,mod);
        int y=balancedOfTreesHeightH(storage,height-2,mod);
        long value1=(long)x*x;
        long value2=(long)y*x*2;
        int res1=(int)(value1%mod);
        int res2=(int)(value2%mod);
        storage[height]=(res1+res2)%mod;
        return storage[height];

    }
}