题目描述

译自 POI 2007 Stage 3. Day 2「Quaternary Balance」

有无限个质量为 $4$ 的幂的砝码，给定正整数 $n$，在使用的砝码数量尽可能少的情况下，求称量重量为 $n$ 的金子的方案数。

输入格式

一行一个正整数 $n (1 \le n \le 10^{1000})$，表示金子的重量。

输出格式

一行一个正整数，表示不同的称量方式对 $10^9$ 的模。

样例

166

3

至少需要 $7$ 个砝码来称量重量为 $166$ 的金子。有以下三种方案：

• 左盘放金子，右盘放重量为 $64, 64, 16, 16, 4, 1, 1$ 的砝码；
• 左盘放金子和重量为 $64, 16, 16$ 的砝码，右盘放重量为 $256, 4, 1, 1$ 的砝码；
• 左盘放金子和重量为 $64, 16, 4, 4, 1, 1$ 的砝码，右盘放重量为 $256$ 的砝码。