题目描述

Byteasar the dragon intends to throw a party, to which he would like to invite many guests. Byteasar wouldalso like to present each guest with an amount of gold to honour the party. Each should receive the sameamount, so that no one's pride is hurt. The dragon is going to weigh out gold for subsequent guests with abeam balance. He has different types of standard masses at his disposal, each type weighing a certain powerof four. Conveniently, Byteasar has lots of the standard masses, hence he may use any number of masses ofany type (power of four) he finds appropriate. Byteasar will always lay the gold on the left weighing basinand the masses on the right or both weighing basins. The dragon wishes to use the least number of massespossible for each weighing. Furthermore, to entertain his guests, Byteasar would like to measure out the goldin unique manner for each person (ie. using different masses or distributing them among the weighing basinsin a different way).

Since dragons' lack of arithmetic skills is legendary, Byteasar has aksed you to write a programme thatwill determine how many guests he may invite, that is, finds the maximum number of ways in which $n$ grammes of gold can be weighed out using the minimum number of masses possible. Should you fare well,you will also get your share!

TaskWrite a programme that:

reads from the standard input the amount of gold (in grammes) which Byteasar intends to present each guest with, calculates the number of ways in which this amount of gold can be weighed out using the minimum number of masses possible, writes out the remainder of dividing the result by $10^9$ to the standard output.

给定一个数 $n$，要求将 $n$ 表示成一些 $4^k$ 的数之和/差的形式，要求用的数最少，求方案数模 $10^9$ 的结果。

输入格式

In the first and only line of the standard input there is one positive integer $n$($1\le n<10^{1000}$).

It is the amountof gold (in grammes) which Byteasar intends to present each guest with.

输出格式

One integer should be written out to the standard output -the remainder of dividing by $10^9$ the maximumnumber of guests Byteasar can invite (that is, the maximum number of ways in which $n$ grammes of gold canbe weighed out using the minimum number of masses possible).

166

3