2663. 「POI2007 R3」四进制天平 Quaternary Balance

传统
$200$ ms
$32$ MiB
$58$ 通过
$118$ 提交

题目描述

译自 POI 2007 Stage 3. Day 2「Waga czwórkowa」

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

输入格式

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

输出格式

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

样例

输入

166

输出

3

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

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