Untitled

class Solution {
    int[] dp = new int[100000];
    int Modd = (int)(1e9 + 7);
    
    public int countHousePlacements(int n) {
        Arrays.fill(dp, -1);
        int x = solve(0, n);  // Already modded in solve
        return (int)((1L * x * x) % Modd);  // Prevent overflow during squaring
    }
    
    public int solve(int idx, int n) {
        if (idx >= n) return 1;
        if (dp[idx] != -1) return dp[idx];
        int option1 = solve(idx + 1, n);
        int option2 = solve(idx + 2, n);
        return dp[idx] = (option1 + option2) % Modd;
    }
}