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.
Input
The first line of the input is an integer N (4<=N<=1000), which denotes the number of chairs.
The next line is an integer K (1<=K<=N), which denotes the number of attendants to the meeting.
Output
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.
Example
Input: 4
2
Output: 2
hide comments
amulyagaur:
20171213 13:47:03
AC in 1 go :) 

Ouditchya Sinha:
20130627 18:04:36
Finally AC with good time in python!!! :) 

Abhishek Mishra:
20120111 18:36:45
my case fails at 20 plzz give reason why it is so 

Divanshu:
20111127 18:39:27
I'm failing on test case 19..


biQar:
20111030 11:22:26
@vivek yadav  for n=100 && k=48 ans is 520625 

vivek yadav:
20110122 01:37:24
what is answer if n=100 && k=48?? 

yyf:
20110122 01:37:24
if 2k>n then ans=0 

Billy Pramboro:
20110122 01:37:24
i think that N ≥ 2K. Last edit: 20110114 11:00:02 

Shizuo Heiwajima:
20110122 01:37:24
How if K==N?


yyf:
20110122 01:37:24
if k=1 then ans=N 
Added by:  Lawl 
Date:  20110106 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Based on a problem in 2010 KOI High School & Middle School Division 