2673: 高二学堂

在美丽的中山纪念中学中，有座高二学堂，同样也是因为一个人，让它们变成了现在这个样子~那就是我们伟大的级主任。

因为他，我们又迎来了一个木有电影，只有对答案的段考日；又迎来了一个不是大礼拜，而是小礼拜的周末。因为是小礼拜，同学们都不回家，所以干脆就回到宿舍去玩牌了。而由于三国杀太out了，所以现在他们都玩四国杀。

四国杀（说白了就是扑克牌~）是Wayne发明的，源于他对升级、斗地主、锄大地等等玩法都感到厌倦了。于是他提出了这个新的玩法：

Wayne有一副加强版的扑克牌，强大到任意取一个自然数x，在牌堆里都恰有4张数值为x的牌。每次，Wayne随机生成两个正整数n和k，然后在牌堆里选取不超过k张牌，使得牌面数字之和恰为n。已知Wayne玩了若干盘，每盘都算出了对应的方案数，他想请你也算出各盘方案数，以验算他的结果是否正确。

结果可能比较大，你只需要求出方案数mod 1000000009的值即可。

包含不超过10组数据。

每行包含两个整数，表示上文中的n和k。

输入数据以两个0表示结束。

每组数据输出一行，为对应的方案数。

2 1
2 2
2 3
50 5
0 0

4
10
10
1823966