题目描述
给定 $n$ 和 $k$。计算有多少长度为 $k$ 的数组 $a_1,a_2\dots, a_k$,满足:
- $\sum_{i=1}^k a_i=n, a_i\geq 0$。
- 对于任意的 $i=1,\dots,k-1$ 有 $a_i~\mathrm{AND}~a_{i+1}=a_{i+1}$。其中AND是与操作。
输出答案对$10^9+7$取模的结果。
输入格式
第一行两个整数$k, n$。
输出格式
一个整数,表示答案。
样例输入1
4 2
样例输出1
2
样例输入2
1919 810
样例输出2
501617298
数据规模
共10个测试点。
测试点$1, 2$满足$n, k\leq 10$。
测试点$3, 4$满足$n, k\leq 100$。
测试点$5, 6$满足$n, k\leq 1000$。
对于所有数据,满足$1\leq n, k\leq 10^4$。