# P3464 [POI2007]WAG-Quaternary Balance

• 7通过
• 17提交
• 题目提供者 洛谷
• 评测方式 云端评测
• 标签 动态规划,动规,dp 进制 POI 2007 高性能
• 难度 提高+/省选-
• 时空限制 1000ms / 128MB
• 提示：收藏到任务计划后，可在首页查看。

## 题目描述

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!

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的数之和/差的形式，要求用的数最少，求方案数

## 输入输出格式

输入格式：

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).

## 输入输出样例

输入样例#1： 复制
166
输出样例#1： 复制
3
提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。