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

Limits: 2 sec., 256 MiB

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

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

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

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

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

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

Input

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

Output

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

Constraints

\(1 \le k, n \le 10^6\),

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
3 2	4

Notes

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

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

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

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

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