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

Added by:Lawl
Date:2011-01-06
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

hide comments
2017-12-13 13:47:03
AC in 1 go :)
2013-06-27 18:04:36 Ouditchya Sinha
Finally AC with good time in python!!! :)
2012-01-11 18:36:45 Abhishek Mishra
my case fails at 20 plzz give reason why it is so
2011-11-27 18:39:27 Divanshu
I'm failing on test case 19..
any special test cases?
2011-10-30 11:22:26 biQar
@vivek yadav - for n=100 && k=48 ans is 520625
2011-01-22 01:37:24 vivek yadav
what is answer if n=100 && k=48??
2011-01-22 01:37:24 yyf
if 2k>n then ans=0
2011-01-22 01:37:24 Billy Pramboro
i think that N ≥ 2K.

Last edit: 2011-01-14 11:00:02
2011-01-22 01:37:24 Shizuo Heiwajima
How if K==N?

Problem Uploader: You simply output 0.

Last edit: 2011-01-14 22:45:18
2011-01-22 01:37:24 yyf
if k=1 then ans=N
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.