#537색상환에서 색 고르기

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

그림 1. 먼셀의 20색상환

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

주어진 색상환에서 시각적 대비 효과를 얻기 위해 서로 이웃하지 않은 색들을 고르는 경우의 수를 생각해 보자. 먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 있도록 10개의 색을 고르는 경우의 수는 2이지만, 11개 이상의 색을 고르면 이웃하지 않게 선택할 수 없으므로 이 경우의 수는 0이다.

정수 N과 K가 주어질 때, N개의 색으로 이루어진 색상환(N색상환)에서 서로 이웃한 두 색을 동시에 고르지 않으면서 서로 다른 K개의 색을 고르는 경우의 수를 구하는 프로그램을 작성하시오.

입력의 첫째 줄에 색상환에 포함된 색의 개수를 나타내는 양의 정수 N(4 ≤ N ≤ 1,000)이 주어지고, 둘째 줄에 N색상환에서 고를 색의 개수 K(1 ≤ K ≤ N)가 주어진다.

첫째 줄에 N색상환에서 서로 이웃한 두 색을 동시에 고르지 않으면서 K개의 색을 고르는 경우의 수를 1,000,000,003 (10억 3)으로 나눈 나머지를 출력한다.