题目描述

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

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

输入格式

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

输出格式

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

166

3