Colored cards

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Having arrived at the programming world semifinal, Zenyk decided it was time to play a board game with the following rules:

• Zenyk thinks of a number \(n\);

• his colleagues have cards of \(k\) colors, for each color there is one card with values 1, 2, 4, ..., \(2^i\), ...;

• they must choose a set of cards such that the sum of their values equals \(n\).

Zenyk became curious about how many different ways there are to choose a set. Two sets are considered different if one set contains a card that is not in the other.

Help Zenyk and count the number of card sets in which the sum of values equals \(n\). Since the answer can be large, output it modulo the prime number \(10^9 + 7\).

Input

The single line contains two integers \(n\) and \(k\) — the number Zenyk thought of, and the number of colors, respectively.

Output

In the single line, print an integer — the number of sets that can be used to obtain the number \(n\), modulo \(10^9 + 7\).

Constraints

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

for 7 tests, the constraint holds: \(k = 1\),

for 7 tests, the constraint holds: \(1 < k, n \le 10^3\).

Samples

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

Notes

In the first test, there are four sets:

• the first card of color 1 with value 1, the second — of color 1 with value 2;

• the first card of color 1 with value 1, the second — of color 2 with value 2;

• the first card of color 2 with value 1, the second — of color 1 with value 2;

• the first card of color 2 with value 1, the second — of color 2 with value 2.