
ZOJ Problem Set  2598
When making different calculations we usually use decimal notation. On the other side, computers usually store and process information in binary form. Both decimal and binary notations are special cases of so called base notations. Base notation is the way to represent integer number as the sum of powers of some integer number B called the base of the notation, taken with some coefficients called digits. Thus the weight of the ith digit is proportional to B^{i} (digits being numbered from zero). Most base notations that we use have a nice property  for any particular number the value of each digit is defined unambiguously. For example, consider the number 5. In binary notation the rightmost digit is 1, the next one is 0, the second digit is 1 and all the others are 0. However, this property just follows from the fact that the number of different values for digits is equal to the base of the notation. If we allow more different values for each digit, the uniqueness of representation would be lost. Consider redundant binary notation, where three digits are allowed: 0, 1 and 2. In this notation some particular number may have several representations. For example, 5 can be represented as both 101 and 21. Find out the number of different representations of the given number R in redundant binary notation. Input Input file contains several lines. In each line there is the integral number R (0 <= R <= 10^{100}). A line with R < 0 indicates the end of input, which should not be proceeded. Output For each integer R, output one integer  the number of ways R can can be represented in redundant binary notation. Sample Input 5 7 1 Sample Output 2 1 Author: Andrew Stankevich Source: Andrew Stankevich's Contest #6 