Problem URL: Count number of ways to place houses

One side of the road has no effect on the other side of the road, so we can put house in both side independently. For one side, we could have number of ways as fibonacci sequence. We we calculate the number of ways for both side, we have to multiply them together.

class Solution:
    def countHousePlacements(self, n: int) -> int:
        MOD = 10**9+7
        a, b = 1, 1
        for i in range(n):
            a, b = b, (a+b) % MOD
        return (b*b) % MOD

Time complexity: O(n)
Space complexity: O(1)