龙 Byteasar 打算举办一场派对，并邀请许多客人参加。为了给派对增光添彩，Byteasar 想给每位客人赠送一定重量的黄金。为了不伤及任何人的自尊，每位客人收到的黄金重量必须相同。Byteasar 将使用天平为后续的客人称量黄金。他拥有多种标准砝码，每种砝码的重量都是 4 的幂。方便起见，Byteasar 拥有大量的标准砝码，因此他可以使用任意数量的任意类型（4 的幂）的砝码。Byteasar 总是将黄金放在天平的左盘，将砝码放在右盘或两个盘中。Byteasar 希望每次称量时使用的砝码数量尽可能少。此外，为了娱乐客人，Byteasar 希望以独特的方式为每个人称量黄金（即使用不同的砝码组合，或以不同的方式将它们分配到天平的两个盘中）。

由于龙的算术能力众所周知地差，Byteasar 请你编写一个程序，确定他可以邀请多少位客人，即找出在保证使用最少数量砝码的前提下，称量出 $n$ 克黄金的不同方案数。如果你做得好，你也会得到属于你的那一份！

题目描述

编写一个程序： 从标准输入读取 Byteasar 打算送给每位客人的黄金重量（以克为单位）， 计算在保证使用最少数量砝码的前提下，称量出该重量黄金的不同方案数， * 将结果除以 $10^9$ 的余数输出到标准输出。

输入格式

标准输入的第一行也是唯一一行包含一个正整数 $n$，$1 \le n < 10^{1000}$。这是 Byteasar 打算送给每位客人的黄金重量（以克为单位）。

输出格式

输出一个整数，即最大可邀请客人数（即在保证使用最少数量砝码的前提下，称量出 $n$ 克黄金的不同方案数）除以 $10^9$ 的余数。

样例

样例输入 1

166

样例输出 1

3

说明

称量 166 克黄金需要 7 个砝码。称量方式如下： 1. 黄金放在左盘；砝码 64, 64, 16, 16, 4, 1, 1 放在右盘。 2. 黄金和砝码 64, 16, 16 放在左盘；砝码 256, 4, 1, 1 放在右盘。 3. 黄金和砝码 64, 16, 4, 4, 1, 1 放在左盘；砝码 256 放在右盘。