Problem J
Prime Bitcount

Image by all_about_people (Shutterstock); Used under license

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.


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 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
Sample Input 2 Sample Output 2
5 5

Please log in to submit a solution to this problem

Log in