계단 화단의 짝수 화분

문제

계단식 화단은 위에서부터 1단, 2단, 3단… 으로 내려가며 한 단마다 화분이 하나씩 늘어납니다. 각 화분에 심는 모종 수는 다음 규칙으로 정합니다.

• 각 단의 양 끝 화분에는 모종을 1개 심는다.
• 그 외의 화분에는 바로 윗단에서 왼쪽 위·오른쪽 위에 맞닿은 두 화분의 모종 수를 더한 만큼 심는다.

1단:            1
2단:          1   1
3단:        1   2   1
4단:      1   3   3   1
5단:    1   4   6   4   1
6단:  1   5  10  10   5   1

단 번호 layer(1부터 시작)가 주어질 때, 그 단에서 모종 수가 짝수인 화분이 몇 개인지 반환하는 solution(layer)를 구현하세요.

예시

제약 조건

• 1 ≤ layer ≤ 50
• 모종 수는 최대 약 6.3 × 10^13 으로 안전한 정수 범위 안입니다

시간 복잡도 목표: O(layer²)