题目描述

给定 $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$。