PrimeStrings

In this problem we deal with binary representations of integers. For clarity, decimal numbers will be given as numbers and their binary representations as strings. For example, the binary representation of 47 is "101111".

Additionally, in the entire problem statement, k is a positive integer constant. (The value of k will be given to you as one of the inputs.)

Let A be a positive integer. Consider the following process:

1. Find the string S that is the binary representation of A.
2. Let L = max( 1, length(S)-k ).
3. Let T be any (not necessarily contiguous) subsequence of S such that the length of T is between 1 and L, inclusive.
4. Convert T to decimal and output the result.

Each integer B that can be the result of the above process is called a binary substring of A. Note that S never starts with a leading zero, but T might. Some examples are shown below.

• Let A = 10 and k = 1.
  1. We convert A to S = "1010".
  2. Then we compute that L = 3, which means that we are interested in subsequences of length at most 3.
  3. Hence, T is one of "0", "1", "00", "01", "10", "11", "010", "100", "101", or "110".
  4. This means that the binary substrings of A are 0, 1, 2, 3, 4, 5, and 6.
• Let A = 10 and k = 2. Now we have L = 2, which means that the possible values of T are "0", "1", "00", "01", "10", and "11". Thus, the binary substrings of A are 0, 1, 2, and 3.
• For A = 10 and k >= 3 the only binary substrings of A are the integers 0 and 1.
• For A = 15 and k = 1 the binary substrings of A are the integers 1, 3, and 7.

You are given the int k. You are also given longs x and y. Consider the integers between 1 and x, inclusive, such that their largest binary substring is smaller than or equal to y.

Compute and return the number of such integers.