Color Wheel
InterviewTime limit1sMemory limit128 MB
Count the ways to choose K non-adjacent colors from N colors arranged in a circle, modulo 1,000,000,003.
- Level
Medium4 of 10
- Topics
- Combinatorics, Math, Dynamic programming
- Solved
- No attempts yet
Problem
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.
Input
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.
Output
Print the number of ways to choose K colors without choosing any adjacent pair, modulo 1,000,000,003.