SP8139 CHAIR - Chairs

N chairs are placed in a circle. There will be K attendants to a very important meeting. However, the attendants do not like each other, so they do not want to sit beside each other in the meeting. As the host of this important meeting, you want to find out how many ways there are to choose K chairs such that none of them are adjacent to each other.

The first line of the input is an integer N (4

Output the total number of ways to choose K chairs from N chairs such that none of the chairs are adjacent. Since the answer can get very large, output the answer modulo 1,000,000,003.