Кольорові карти

Обмеження: 2 сек., 256 МіБ

Приїхавши на півфінал світу з програмування, Зеник вирішив, що час зіграти в настільну гру з такими правилами:

• Зеник загадує число $n$;

• його колеги мають карти $k$ кольорів, для кожного кольору є по одній карті зі значеннями 1, 2, 4, ..., $2^i$, ...;

• вони повинні взяти набір карт так, аби сума їх значень була рівна $n$.

Зенику стало цікаво, скільки ж є різних способів вибрати набір. Два набори вважаються різними, якщо в одному наборі є карта, якої немає в іншому.

Допоможіть Зенику і порахуйте кількість наборів карт, у яких сума значень рівна $n$. Оскільки відповідь може бути великою, виведіть її за модулем простого числа $10^9 + 7$.

Вхідні дані

У єдиному рядку задано два цілих числа $n$ та $k$ — число, яке загадав Зеник, та кількість кольорів відповідно.

Вихідні дані

У єдиному рядку виведіть ціле число — кількість наборів, якими можна отримати число $n$, за модулем $10^9 + 7$.

Обмеження

$1 \le k, n \le 10^6$,

для 7 тестів виконується обмеження: $k = 1$,

для 7 тестів виконується обмеження: $1 < k, n \le 10^3$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 2	4

Примітки

У першому тесті є чотири набори:

• перша карта кольору 1 зі значенням 1, друга — кольору 1 зі значенням 2;

• перша карта кольору 1 зі значенням 1, друга — кольору 2 зі значенням 2;

• перша карта кольору 2 зі значенням 1, друга — кольору 1 зі значенням 2;

• перша карта кольору 2 зі значенням 1, друга — кольору 2 зі значенням 2.