Color Wheel

A color wheel arranges representative colors in a ring. The 20-color wheel designed for education by the American painter Munsell is widely known. The image below shows Munsell's 20-color wheel.

Figure 1. Munsell's 20-color wheel

Two neighboring colors on a color wheel are similar and can be hard to distinguish at a glance. In the figure above, scarlet is adjacent to red and orange, and grass green is adjacent to yellow-green and green. To create visual contrast, no two neighboring colors will be used together.

Given a color wheel made of N colors, compute the number of ways to choose K distinct colors so that no two chosen colors are adjacent. For instance, on Munsell's 20-color wheel there are 2 ways to choose 10 colors with visual contrast, but it is impossible to choose 11 or more colors under this condition, so the count is 0.

The first line contains a positive integer N (4 <= N <= 1,000), the number of colors in the color wheel. The second line contains K (1 <= K <= N), the number of colors to choose.

Print the number of ways to choose K colors without choosing any adjacent pair, modulo 1,000,000,003.