서로 다른 \(N\)개의 색이 원형으로 배치된 색상환이 있다. 각 색은 양옆의 색과 서로 인접한다. 따라서 첫 번째 색과 \(N\)번째 색도 서로 인접한다.

예를 들어 8개의 색이 배치된 색상환은 다음과 같이 나타낼 수 있다. 선으로 직접 연결된 두 색은 서로 인접한 색이다.

색상환에서 \(K\)개의 색을 선택하려고 한다. 선택한 색 가운데 서로 인접한 두 색이 존재해서는 안 된다.

색을 선택하는 순서는 구분하지 않는다. 즉, 선택한 색의 집합이 같다면 하나의 방법으로 센다.

조건을 만족하도록 \(K\)개의 색을 선택하는 경우의 수를 구하는 프로그램을 작성하시오.

미리 작성된 코드

다음 코드는 미리 작성되어 있다.

#include <stdio.h>

int dt[1001][1001];
int n, k;
int mod = 1000000003;

int main() {
    scanf("%d %d", &n, &k);

    // 코드를 작성하세요.

    printf("%d\n", dt[n][k]);
    return 0;
}

제출 방법

// 코드를 작성하세요. 부분에 들어갈 코드만 제출한다.

입력을 받는 코드와 출력하는 코드는 제출하지 않는다.

입력

첫째 줄에 색의 수 \(N\)이 주어진다.

둘째 줄에 선택할 색의 수 \(K\)가 주어진다.

출력

조건을 만족하는 선택 방법의 수를 \(1,000,000,003\)으로 나눈 나머지를 출력한다.

제한 사항

• \(4 \le N \le 1,000\)
• \(1 \le K \le N\)

예제 입력 1

4
2

예제 출력 1

2

예제 설명 1

서로 마주 보는 두 색을 선택하는 두 가지 방법이 있다. 서로 이웃한 두 색을 선택하는 방법은 조건을 만족하지 않는다.

예제 입력 2

5
2

예제 출력 2

5

예제 설명 2

각 색에서 시작하여 바로 이웃하지 않은 색 하나를 선택하면 총 5가지 방법을 만들 수 있다.