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

Обмеження: 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.