# 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 |