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) | Output (stdout) |
|---|---|
| 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.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
Colored cards - Editorial
If \(k = 1\), there is only one way to split \(n\) into powers of two: the binary representation of the number.
Suppose we know a split of \(n\) into \(a_1, \ldots, a_k\), where \(a_i\) is the sum of the cards of color \(i\). Each such split corresponds to exactly one set of cards, and each set of cards corresponds to exactly one such split, so the number of sets of cards summing to \(n\) equals the number of splits of \(n\) into \(a_1, \ldots, a_k\). And the number of such splits is the number of combinations with repetition (you can read more about it here). So the number of combinations with repetition is \(C_{n+k-1}^{k-1}\), a binomial coefficient that can be computed modulo the given number in many ways.
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|