月饼方案

题目描述

33DAI 有 $63$ 种月饼，编号从 $0$ 到 $62$ ，第 $i$ 种月饼的重量为 $2^i$ 。每种月饼都有无限个。

$2^i$ 表示 $i$ 个 $2$ 相乘。例如 $2^0=1$ ， $2^1=2$ ， $2^2=2\times2=4$ ， $2^{10}=1024$ 。

注意：因为 $x< 2^{27}< 2^{62}$ ，编号较大的月饼不会用上，给出的 $63$ 种足够用。

33DAI 想要送给 Tom 重量之和恰好为 $x$ 的月饼，求有多少种方案。

两种方案不同，当且仅当存在某个编号 $i$ ，使得两种方案中编号为 $i$ 的月饼个数不同。方案与选取月饼的先后顺序无关。

由于答案可能很大，请把答案对 $2^{32}$ 取余后输出。

一行一个整数 $x$ 。

一行一个整数，表示方案数对 $2^{32}$ 取余的结果。

样例 1： $x=3$ ，有两种方案： $3=1+1+1$ （三个编号为 $0$ 的月饼）， $3=2+1$ （一个编号为 $1$ 的月饼和一个编号为 $0$ 的月饼）。

样例 2： $x=4$ ，有四种方案： $4=1+1+1+1$ ， $4=2+1+1$ ， $4=2+2$ ， $4=4$ 。

对于全部数据， $1\le x< 2^{27}$ （即 $1\le x\le 134217727$ ）。

每个子任务的计分方式为 min（取该子任务中所有测试点的最低分）。

子任务之间存在依赖：子任务 2 依赖子任务 1，子任务 3 依赖子任务 2。即只有通过了所依赖的子任务，该子任务才能得分。