AND Operation Arrays

Problem Description

Given $n$ and $k$. Count how many arrays $a_1, a_2, \dots, a_k$ of length $k$ satisfy:

• $\sum_{i=1}^k a_i = n$, with $a_i \ge 0$.
• For every $i = 1, \dots, k-1$, $a_i\ \mathrm{AND}\ a_{i+1} = a_{i+1}$, where $\mathrm{AND}$ denotes the bitwise AND operation.

Output the answer modulo $10^9 + 7$.

Input Format

The first line contains two integers $k, n$.

Output Format

One integer — the answer.

Sample Input 1

4 2

Sample Output 1

2

Sample Input 2

1919 810

Sample Output 2

501617298

Constraints

There are 10 test points in total.

• Test points 1, 2 satisfy $n, k \le 10$.
• Test points 3, 4 satisfy $n, k \le 100$.
• Test points 5, 6 satisfy $n, k \le 1000$.

For all data, $1 \le n, k \le 10^4$.