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

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

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

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

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

至少需要 $7$ 个砝码来称量重量为 $166$ 的金子。有以下三种方案： * 左盘放金子，右盘放重量为 $64, 64, 16, 16, 4, 1, 1$ 的砝码； * 左盘放金子和重量为 $64, 16, 16$ 的砝码，右盘放重量为 $256, 4, 1, 1$ 的砝码； * 左盘放金子和重量为 $64, 16, 4, 4, 1, 1$ 的砝码，右盘放重量为 $256$ 的砝码。