2177. Or Link

【题目描述】

给定两个整数 N 和 K。

请你计算有多少长度为 K 的序列 A1, A2, ..., AK，(0<=Ai) 满足：

    A1+ A2+ ...+ AK = N。

并且对于任意的 i = 1, ..., k - 1 有 Ai  Or  Ai + 1 = Ai + 1。

【提示】

Or 是按位或操作。

Pascal 为 or  ，C 和 C++为 |。

【输入格式】

此题有多组数据。

第一行包含一个整数 T ，表示测试数据组数。

接下来有 T 行，每行包括两个整数 N 和 K ,意义如题目所述。

【输出格式】

对于每组测试数据，输出一行表示对应的答案。考虑答案可能很大，输出模 1000000009 后的结果。

【样例输入】

3

2 3

2 4

3 3

【样例输出】

2

2

2

【样例解释】

对于第一个数据，有两种方案：（0，1，1），（0，0，2）；

对于第二个数据，有两种方案：（0，0，1，1），（0，0，0，2）；

对于第三个数据，有两种方案：（1，1，1），（0，0，3）。

【数据范围】

对于10%的数据，N<=10,K<=10 ；

对于30%的数据，N<=100,K<=1000 ；

对于50%的数据，N<=10000,K<=100000 ；

对于70%的数据，N<=1000000,K<=10000000 ；

对于100%的数据，N<=10000000,K<=1000000000，T<=100 。

【来源】

改编自 hihoCoder Challenge 5 .