Solução escrita por Márcio Vitor
Conhecimentos prévios:
Vamos usar programação dinâmica para resolver o problema! 🙂
Seja $dp[i]$ = quantas formas podemos preencher por completo um tabuleiro de tamanho $3 x i$, usando as peças disponíveis, podemos transicionar para 3 tamanhos:
Caso base: $dp[0] = 1$
$dp[i] = dp[i-1] + 2 \cdot dp[i-2] + 2 \cdot dp[i-3]$, complexidade final: $\mathcal{O}(N)$
Nota: Não esqueça de tirar o resto da divisão mod $10^9 + 7$.