Description

Byteasar the dragon plans to throw a party and give each guest the same amount of gold so that no one feels slighted. He will weigh the gold for each guest using a beam balance. He has standard masses whose weights are powers of four. Conveniently, he has an unlimited supply of each type of mass (each power of four). Byteasar will always place the gold on the left pan, and he may place masses on the right pan or on both pans. He wants to use the fewest masses possible for each weighing. Moreover, to entertain his guests, he would like to measure the gold in a unique way for each person (i.e., using different masses or distributing them between the pans differently).

Since dragons are not known for arithmetic, Byteasar asks you to write a program to determine how many guests he can invite, i.e., the maximum number of ways to weigh out $n$ grams of gold using the minimum number of masses possible. You should output the result modulo $10^9$.

In other words, given a number $n$, express $n$ as a sum and/or difference of numbers of the form $4^k$, using the fewest terms, and count the number of such representations, modulo $10^9$.

Input Format

The first and only line contains one positive integer $n$ ($1 \le n < 10^{1000}$), the amount of gold in grams Byteasar intends to give each guest.

Output Format

Print one integer: the remainder modulo $10^9$ of the maximum number of ways to weigh out $n$ grams using the minimum number of masses possible.

166

3

Hint

Translated by ChatGPT 5