#P1111. [POI2007]四进制的天平Wag

    ID: 116 传统题 1000ms 128MiB 尝试: 362 已通过: 209 难度: 6 上传者: 标签>CF1900普及+/提高-进位制转换高精度除法线性 DP计数 DP滚动数组

[POI2007]四进制的天平Wag

题目描述

Mary 准备举办一个聚会,她准备邀请很多的人参加她的聚会。并且她准备给每位来宾准备一些金子作为礼物。为了不伤及每个人的脸面,每个人获得的金子必须相同。

Mary 将要用一个天平来称量出金子。她有很多的砝码,所有砝码的质量都是4的幂。Mary 将金子置于左边并且将砝码置于右盘或者两个盘。她希望每次称量都使用最少的砝码。并且,他希望,每次都用不同的称量方法称出相同质量的金子。

对于给定的质量 nn,Mary 希望知道最少需要用多少个砝码可以完成称量,并且想知道用这么多个砝码一共有多少种方式进行称量。

输入格式

输入文件仅包含一个整数 n(1≤n≤101000)n(1 \le n \le 10^{1000}),表示Mary希望给每个人的金子的质量。

输出格式

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

166
3

样例解释

一共有三种方式称量出166。

166=64+64+16+16+4+1+1166=64+64+16+16+4+1+1,

166=256−64−16−16+4+1+1166=256-64-16-16+4+1+1,

166=256−64−16−4−4−1−1166=256-64-16-4-4-1-1。

提示

没有写明提示