구글해서 참고해 보시는게 그림도 있어서 좋긴 합니다.
어짜피 코딩문제라기보다는 수학문제에 가까워서 점화식만 알면 엄청 쉽습니다.
아마 n=8까지 값만 알려줬어도 그냥 점화식 level 1로 풀 수 있었을것이라 생각합니다.

여기에 설명하자면, 기본적으로 n크기 도형은 n-2크기 도형에 2크기 3가지를 오른쪽에 붙이는 것으로 3*f(n-2) 개가 있습니다.

그리고 x 사이즈(x는 n이하) 모양의 상자모양에 대해서, 그 왼쪽에 n-x 크기 도형을 붙이는 형태가 만들어집니다.
x 사이즈 상자모양은 전부 2개씩이므로 2f(n-4)+2f(n-6)+....+f(2)+2가 됩니다.
이렇게 하는 이유는 n-2크기의 오른쪽에 2크기 3가지를 붙이는 것은 거의 모든 케이스가 포함되지만 상자가 오른쪽 끝에 붙은 형태만 빠져있기 때문입니다.

최종적으로 f(n)=3f(n-2)+2f(n-4)+2*f(n-6)+....+f(2)+2가 전체 점화식이 됩니다.

이때, f(n-2)-f(n-4)= 2f(n-4)+2f(n-6)+....+f(2)+2 이기 때문에 오른쪽 전체를 f(n-2)-f(n-4)로 대체하면,
f(n) = 4*f(n-2)-f(n-4)가 가장 간략하고 연산량이 적은 점화식이라고 할 수 있습니다.

파이썬 같은 경우 정수형이 수만 자리여도 연산을 해주니까 마지막에만 나머지를 써도 되지만 조금 더 효율적으로 계산하려면 다른 질문의 내용을 참고해보시면 좋겠습니다.