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

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.