501008 - 贵重的礼物

【题目描述】贵重的礼物（balance）

琳琳准备举办一个聚会，她准备邀请很多的人参加她的聚会。并且她准备给每位来宾准备一些金子作为礼物。为了不伤及每个人的脸面，每个人获得的金子必须相同。琳琳将要用一个天平来称量出金子。她有很多的砝码，所有砝码的质量都是4的幂。 琳琳将金子置于左边并且将砝码置于右盘或者两个盘。她希望每次称量都使用最少的砝码。并且她希望，每次都用不同的称量方法称出相同质量的金子。对于给定的质量n，琳琳希望知道最少需要用多少个砝码可以完成称量，并且想知道用这么多个砝码一共有多少种方式进行称量。

输入仅包含一个整数，表示琳琳希望给每个人的金子的质量。（1≤n≤10^1000）

输出仅包含一个整数，表示一共可能的称量方式对10^9的模。

一共有三种方式称量出166。即： 166＝64＋64＋16＋16＋4＋1＋1 166＝256－64－16－16＋4＋1＋1 166＝256－64－16－4－4－1－1