In how many ways can we paint $16$ seats in a row, each red or green, in such a way that the number of consecutive seats painted in the same colour is always odd?

Let's think step by step and output the final answer within \boxed{}.
user