There is a street with n * 2 plots, where there are n plots on each side of the street. The plots on each side are numbered from 1 to n. On each plot, a house can be placed.

Return the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street. Since the answer may be very large, return it modulo 109 + 7.

Note that if a house is placed on the ith plot on one side of the street, a house can also be placed on the ith plot on the other side of the street.

&nbsp;
Example 1:

Input: n = 1
Output: 4
Explanation: 
Possible arrangements:
1. All plots are empty.
2. A house is placed on one side of the street.
3. A house is placed on the other side of the street.
4. Two houses are placed, one on each side of the street.


Example 2:

Input: n = 2
Output: 9
Explanation: The 9 possible arrangements are shown in the diagram above.


&nbsp;
Constraints:


	1 &lt;= n &lt;= 104


class Solution:
    def countHousePlacements(self, n: int) -> int:
        
        
        @lru_cache(None)
        def rec(i, k):
            
            # i is the index of the house 
            # k is the state of last house, 1 if there was a house on the last index else 0
            
            if i>=n:
                return 1
            
            elif k==0:
                return rec(i+1,1) + rec(i+1,0)
            
            else:
                return rec(i+1,0)
        
        
        
        #l1 are the combinations possible in lane 1, the final answer will be the square 
		#of of l1 as for every combination of l1 there will be "l1" combinations in lane2.
        
        l1 = rec(1,0) + rec(1,1)
        
        
        mod = 10**9 +7
        return pow(l1, 2, mod) #use this when there is mod involved along with power 
            
class Solution {
    int mod = (int)1e9+7;
    public int countHousePlacements(int n) {
        
        if(n == 1)
            return 4;
        if(n == 2)
            return 9;
        long a = 2;
        long b = 3;
        if(n==1)
            return (int)(a%mod);
        if(n==2)
            return (int)(b%mod);
        long c=0;
        for(int i=3;i<=n;i++)
        {
            c = (a+b)%mod;
            a=b%mod;
            b=c%mod;
        }
        
        return (int)((c*c)%mod);
    }
}
class Solution {
public:
    typedef long long ll;
    ll mod = 1e9+7;
    int countHousePlacements(int n) {
        ll house=1, space=1;
        ll total = house+space;
        for(int i=2;i<=n;i++){
	        house = space;
	        space = total;
	        total = (house+space)%mod;
	    }
	    return (total*total)%mod;
    }
};
const mod = (10 ** 9) + 7
var countHousePlacements = function(n) {
    let prev2 = 1
    let prev1 = 1
    let ways = 2
    
    for ( let i = 2; i <= n; i++ ) {
        prev2 = prev1
        prev1 = ways
        ways = ( prev1 + prev2 ) % mod
    }
    
    return (ways ** 2) % mod
}
Count Number of Ways to Place Houses