Redundant binary notation is similar to binary notation, except instead of allowing only ’s and ’s for each digit, we allow any integer digit in the range , where t is some specified upper bound. For example, if , the digit  is permitted, and we may write the decimal number  as , , or . If , every number has precisely one representation, which is its typical binary representation. In general, if a number is written as  in redundant binary notation, the equivalent decimal number is .

    Redundant binary notation can allow carryless arithmetic, and thus has applications in hardware design and even in the design of worst-case data structures. For example, consider insertion into a standard binomial heap. This operation takes  worst-case time but  amortized time. This is because the binary number representing the total number of elements in the heap can be incremented in worst-case time and amortized time. By using a redundant binary representation of the individual binomial trees in a binomial heap, it is possible to improve the worst-case insertion time of binomial heaps to .

    However, none of that information is relevant to this question. In this question, your task is simple. Given a decimal number and the digit upper bound , you are to count the number of possible representations has in redundant binary notation with each digit in range with no leading zeros.