{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"Larry is very bad at math — he usually uses a calculator, which worked well throughout college. Unfortunately, he is now struck in a deserted island with his good buddy Ryan after a snowboarding accident.\n\u003cbr\u003e\u003cbr\u003e\nThey’re now trying to spend some time figuring out some good problems, and Ryan will eat Larry if he cannot answer, so his fate is up to you!\n\u003cbr\u003e\u003cbr\u003e\nIt’s a very simple problem — given a number N, how many ways can K numbers less than N add up to N?\n\u003cbr\u003e\u003cbr\u003e\nFor example, for N \u003d 20 and K \u003d 2, there are 21 ways:\n\u003cul type\u003d\"none\"\u003e\n\u003cli\u003e0+20\u003c/li\u003e\n\u003cli\u003e1+19\u003c/li\u003e\n\u003cli\u003e2+18\u003c/li\u003e\n\u003cli\u003e3+17\u003c/li\u003e\n\u003cli\u003e4+16\u003c/li\u003e\n\u003cli\u003e5+15\u003c/li\u003e\n\u003cli\u003e...\u003c/li\u003e\n\u003cli\u003e18+2\u003c/li\u003e\n\u003cli\u003e19+1\u003c/li\u003e\n\u003cli\u003e20+0\u003c/li\u003e\n\u003c/ul\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Each line will contain a pair of numbers \u003ci\u003eN\u003c/i\u003e and \u003ci\u003eK\u003c/i\u003e. \u003ci\u003eN\u003c/i\u003e and \u003ci\u003eK\u003c/i\u003e will both be an integer from 1 to 100, inclusive. The input will terminate on 2 \u003ccode\u003e0\u003c/code\u003e’s."}},{"title":"Output","value":{"format":"HTML","content":"Since Larry is only interested in the last few digits of the answer, for each pair of numbers \u003ci\u003eN\u003c/i\u003e and \u003ci\u003eK\u003c/i\u003e, print a single number mod 1,000,000 on a single line."}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable border\u003d\"1px solid\" width\u003d\"100%\" cellpadding\u003d\"4px\" cellspacing\u003d\"0px\"\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003cth width\u003d\"50%\"\u003eSample Input\u003c/th\u003e\n \u003cth width\u003d\"50%\"\u003eSample Output\u003c/th\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd valign\u003d\"top\"\u003e\u003ccode\u003e\n20 2\u003cbr\u003e\n20 2\u003cbr\u003e\n0 0\u003cbr\u003e\n \u003cbr\u003e\u003c/code\u003e\u003c/td\u003e\n \u003ctd valign\u003d\"top\"\u003e\u003ccode\u003e\n21\u003cbr\u003e\n21\u003cbr\u003e\n \u003cbr\u003e\u003c/code\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n\u003c/table\u003e"}}]}