세계의 다양한 요리를 직접 만들어 먹어보는 것을 즐기는 유리가 요즘에는 파스타에 푹 빠졌다.

그래서 매일 저녁 메뉴로 파스타를 만들어 먹는다.

유리가 만들 수 있는 파스타는 세 종류로서 토마토 파스타, 크림 파스타, 미트볼 파스타이다.

유리는 친구들을 초대하여 파스타를 함께 먹기도 하는데 이러한 약속을 포함하여 N일 간의 식단을 짤 생각이다.

같은 종류의 파스타를 매일 먹으면 질릴 수 있으므로 같은 종류의 파스타를 3일 이상 연속하여 먹지 않도록 식단을 짤 생각이다.

또한 K개의 약속한 날에는 정해진 파스타를 만들 생각이다.

N일 동안의 식단을 계획하는 방법은 몇 가지나 될까?

유리와 함께 프로그램을 작성하여 구해보자.

입력 예 1을 예로 보자.

유리는 5일간의 식단을 계획하고 있다. 3개의 약속이 있어서 1일째와 3일째는 토마토 파스타, 4일째는 크림파스타로 정해놓고 생각할 것이다.

편의상 토마토 파스타를 1번, 크림 파스타를 2번, 미트볼 파스타를 3번으로 한다.

파스타(Pasta) timer 1000초 memory 64MB

파스타(Pasta) 1000초 64MB