색상환

색상환은 색을 표현하는 기본 요소로 만들 수 있는 여러 색 중 대표적인 색들을 고리 모양으로 배열한 것이다. 미국 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환이다.

그림 1. 먼셀의 20색상환

색상환에서 서로 이웃한 두 색은 비슷해서 한눈에 구별하기 어렵다. 위 그림에서 다홍은 빨강, 주황과 각각 이웃하고, 풀색은 연두, 녹색과 각각 이웃한다. 시각적 대비 효과를 얻기 위해 서로 이웃한 두 색은 동시에 사용하지 않으려 한다.

N개의 색으로 이루어진 색상환에서 어떤 이웃한 두 색도 동시에 선택하지 않으면서 서로 다른 K개의 색을 고르는 경우의 수를 구하라. 예를 들어 먼셀의 20색상환에서 10개의 색을 고르는 경우의 수는 2이고, 11개 이상의 색은 조건을 만족하도록 고를 수 없으므로 경우의 수는 0이다.

첫째 줄에 색상환에 포함된 색의 개수 N (4 <= N <= 1,000)이 주어진다. 둘째 줄에 선택할 색의 개수 K (1 <= K <= N)가 주어진다.

조건을 만족하며 K개의 색을 고르는 경우의 수를 1,000,000,003으로 나눈 나머지를 출력한다.