Problem J
Prime Bitcount
This problem is very easy to describe. In fact, it is so easy to describe that there is really no need for a preamble such as the one you are reading right now, which makes it surprising that the problem author didn’t just omit this part and skip directly to the Input and Output sections. However, since that is not the case, and since we have your attention, we will take this opportunity to remind you that a substring of a string is, by definition, a contiguous subsequence of characters in the string.
Input
The input consists of a single line containing two space-separated integers, $n$ and $k$, with $2 \leq n \leq 1\, 000$ and $2 \leq k \leq \min (n, 100)$.
Output
Output a single integer: the number of binary strings of length $n$ with the property that every substring of length $k$ contains a prime number of $1$’s. Since the answer may be large, output it modulo the smallest prime number, $p$, such that $p > 10^9$ and the product of $p$’s nonzero (base-$10$) digits is $42$.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 2 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 5 |
21 |
